Archived

This topic is now archived and is closed to further replies.

randomDecay

find and replace text algorithm

Recommended Posts

I was wondering if anyone could help me out here on a programming interview question I recently had. I was told to describe an efficient algorithm for doing a "find and replace" in a text file. I am curious if any of you have any ideas about how you would implement it -- I'm curious. Thanks.

Share this post


Link to post
Share on other sites
Well, I suppose you could always use a brute force algorithm. Go through the text one character at a time, checking for the search text each time. Then once you find it, erase it, then insert the replace text. Continue.

Share this post


Link to post
Share on other sites
Efficient? Well, I'm going to try my hand at it...



char * Replace( char * toReplace, char * replaceWith, char * text ) {

std::list< int > startindices;

int replacedLength = strlen(toReplace);

char * CurrentChar = text;
char * CurrentComparison = toReplace;
int CurrentIndex, replacedCount = 0;

while( *CurrentChar != '\0' ) {
if( *CurrentChar == *CurrentComparison ) {
CurrentComparison++;
if( *CurrentComparison == '\0' ) {
startindices.push_back( CurrentIndex );
CurrentComparison = toReplace;
CurrentIndex += replacedLength;
replacedCount++;
}
CurrentChar++;
}
else {
if( CurrentComparison == toReplace ) {
CurrentChar++;
}
else {
CurrentComparison = toReplace;
}
CurrentIndex++;
}
}

long Delta = strlen(replaceWith) - replacedLength;

newText = (char*)malloc( strlen(text) + replacedCount * Delta );

if( replacedCount == 0 ) {

return( newText );
}

int Index = 0;
char * pNewText = newText;
char * pText = text;
char * pReplaced;

for( std::list<int>::iterator i = startIndices.begin( );
i != startindices.end( );
i++ ) {

for( ; Index < (*i); Index++ ) {
*(pNewText++) = *(pText++);
}

pReplaced = replaceWith;
pText += replacedLength;
Index += replacedLength;

while( *pReplaced != '\0' ) {
*(pNewText++) = *(pReplaced++);
}
}

return( newText );
}


EDIT : that's O(n), and you can't do better.

ToohrVyk



[edited by - ToohrVyk on July 8, 2003 5:38:00 PM]

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
or...
std::string str;

str = LoadFile();
str.replace(What,With);
SaveFile(str);

Share this post


Link to post
Share on other sites
Basically, you make a list of each index in the text where a "to replace" substring starts. Based on this data, you allocate memory for the new string. Then, you copy the text until an index, copy the "replaceWith" string into the final text, skip over the "toreplace" string in the original text, and resume copying until the next index.

Share this post


Link to post
Share on other sites