Jump to content
  • Advertisement

Archived

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

randomDecay

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.

If you intended to correct an error in the post then please contact us.

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
Advertisement
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

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!