#### Archived

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

# find and replace text algorithm

This topic is 5487 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## 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 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 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 on other sites
That''s good stuff, ToohrVyk. Would you mind explaining it a bit? Thanks.

##### Share on other sites
or...
std::string str;
str = LoadFile();str.replace(What,With);SaveFile(str);

##### 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.

1. 1
Rutin
24
2. 2
3. 3
JoeJ
18
4. 4
5. 5

• 38
• 23
• 13
• 13
• 17
• ### Forum Statistics

• Total Topics
631712
• Total Posts
3001849
×