How to find see if one string is located inside of another and replace it?

Question

I need help with the following program. I don't know how to check if occurrences of string2 are inside string1, and then replace them with string3.

Write a function named replaceSubstring. The function should accept three string object arguments. Let’s call them string1, string2, and string3. It should search string1 for all occurrences of string2. When it finds an occurrence of string2, it should replace it with string3. Demonstrate and test the function with a complete program.

For example, suppose the three arguments have the following values:

string1: "the dog jumped over the fence"

string2: "the"

string3: "that"

With these three arguments, the function would return a string object with the value "that dog jumped over that fence". Demonstrate the function in a complete program.

int main()
{
    string string1 = "xyzxyzxyz";
    string string2 = "xyz";
    string string3 = "a";
    replaceSubstring(string1, string2, string3);
    return 0;
}

void replaceSubstring(string string1, string string2, string string3)
{
    string result;
    for (int i = 0; i < string1.length(); i++){
        if (string1.find(string2, i)){
            result = string1.replace(i, string3.length()+i, string3);
        }
    }
    cout << result;

}

Answer 1

A quick way to do this is with the Boost String Algorithms Library as stated here

#include <boost/algorithm/string/replace.hpp>
{ // 1. 
  string test = "abc def abc def";
  boost::replace_all(test, "abc", "hij");
  boost::replace_all(test, "def", "klm");
}


{ // 2.
  string test = boost::replace_all_copy
  (  boost::replace_all_copy<string>("abc def abc def", "abc", "hij")
  ,  "def"
  ,  "klm"
  );
}

Because, as stated here:

There is no one built-in function in C++ to do this. If you'd like to replace all instances of one substring with another, you can do so by intermixing calls to string::find and string::replace. For example: size_t index = 0; while (true) { /* Locate the substring to replace. */ index = str.find("abc", index); if (index == std::string::npos) break;

     /* Make the replacement. */
     str.replace(index, 3, "def");

     /* Advance index forward so the next iteration doesn't pick it up as well. */
     index += 3;
}

If the objective is to implement your own code for replacing matched strings, I would recommend that you read up on Z and KMP algorithms. For a quick and dirty solution, see below Geeks For Geeks:

// C program for Naive Pattern Searching algorithm
#include<stdio.h>
#include<string.h>

void search(char *pat, char *txt)
{
    int M = strlen(pat);
    int N = strlen(txt);

    /* A loop to slide pat[] one by one */
    for (int i = 0; i <= N - M; i++)
    {
        int j;

        /* For current index i, check for pattern match */
        for (j = 0; j < M; j++)
            if (txt[i+j] != pat[j])
                break;

        if (j == M)  // if pat[0...M-1] = txt[i, i+1, ...i+M-1]
           printf("Pattern found at index %d \n", i);
    }
}

/* Driver program to test above function */
int main()
{
   char txt[] = "AABAACAADAABAAABAA";
   char pat[] = "AABA";
   search(pat, txt);
   return 0;
}

After the positions have been found, write a method to build a new string and replace, add, delete characters, one by one starting at the positions.

Answer 2

string.find returns the index of the first character of the found string. Here's a small example.

int main()
    {
    string myString = "ThisMessageIsPointLess";

    string strToFind = "Is";
    size_t idx = myString.find(strToFind.c_str());
    // idx = 11 because 'Is' starts at the 11th position in the string

    idx = myString.find("Foo");
    // idx == std::string::npos because it hasn't found "Foo" in myString

In all cases, you should check that the substring has been found in the string. You just have to compare the index that's being returned with the default failure value from the library:

    if (idx == std::string::npos)
        {
        // Failed to find the substring
        return false;
        }

Now, there are quite a few overloads of std::string::replace and they can do different things. I suggest you use the one that takes two iterators and the 'replacement' string.

    string replacement = "Seems";
    myString.replace(myString.begin() + idx, myString.begin() + idx + strToFind.size(), replacement.c_str());
    // myString = "ThisMessageSeemsPointless"
    return true;

The overload we've used takes the iterator of the first character to replace, the iterator of the last character to replace, and the replacement string. We know that the string starts at idx from the beginning. By simple logic, we know it should end at idx + strToFind.size() from the beginning.

PS: it might be relevant to name your variables so other people understand them more easily. Don't put "string" in the name; its type is string so that's redundant. Consider replacing string2 by token and string3 by newToken or replacement... anything that's more meaningful than numbers.

Last thing, you might want to pass your variables by reference (for string1) and by const-reference (for string2 and string3). This will avoid creating local copies of the strings and should improve overall performance.

bool replaceSubstring(string& string1, string const& string2, string const& string3)

Answer 3

Without any additional library like boost, you need to write a custom replacement algorithm using the std library. This one computes the resulting string as a returned value.

string replaceSubstring(const string& string1, const string& string2, const string& string3)
{
    string result;
    size_t posStart = 0, posFound;
    for(; (posFound = string1.find(string2, posStart)) != string1.npos;
           posStart = posFound + string2.size())
    {
        copy(string1.begin()+posStart, string1.begin()+posFound, back_inserter(result));
        result.append(string3);
    }
    copy(string1.begin()+posStart, string1.end(), back_inserter(result));
    return result;
}

Of course you can easily change it into void by changing the fisrt parameter from const string& string1 to string& string1 and assigning it from the result before returning.

If this code is to run on large strings and if it turns out that the allocations needed by the back-insertion are not correctly optimized by the implementation (a concern raised by @RemyLebeau in the comments), you can make some reservation prior to the copy statements:

...
result.reserve(result.size() + posFound + string3.size() + 2 - posStart);
copy(string1.begin()+posStart, string1.begin() + posFound, back_inserter(result));

...
result.reserve(result.size() + string1.size() + 2 - posStart);
copy(string1.begin()+posStart, string1.end(), back_inserter(result));

Answer 4

Your function has several problems in it:

1. you did not follow the instructions! "the function would return a string object...". your function does not return anything. It just outputs the result to the console screen instead. That should be main()'s responsibility instead.

2. you have the right idea to use std::string::find() and std::replace(), but you are using them both completely wrong.

   • find() returns the index of the substring, or -1 (well, technically std::string::npos) if not found. Any value other than 0 will evaluate as true in an if expression. Your code is assuming that the substring is found at the same index that you are passing into find() as an input parameter, and that is simply not guaranteed.

   • the version of replace() you are calling expects a starting index and the number of characters to replace. You are not passing it the index returned by find(), and you are passing it the wrong character count, too.

   • You are also looping through the input string one character at a time. Replacing substrings within the same input string that you are looping through is going to reek havoc with your looping logic.

With that said, try this instead:

string replaceSubstring(const string &string1, const string &string2, const string &string3)
{
    string result = string1;
    string::size_type pos = 0;
    do
    {
        pos = result.find(string2, pos);
        if (pos == string::npos) break;
        result.replace(pos, string2.length(), string3);
        pos += string3.length();
    }
    while (true);
    return result;
}

int main()
{
    string string1 = "the dog jumped over the fence";
    string string2 = "the";
    string string3 = "that";
    string result = replaceSubstring(string1, string2, string3);
    cout << result;
    return 0;
}