Replace a sub-string with another String in C++

In this article, we will disucss different ways to find and replace any substring in a given string with another string in C++.

Using a char array and pointer arithmetic:

We will be using the following functions in the program:

memcpy():

The memcpy() is a C-style function that copies a specified number of bytes from a source memory location to a destination memory location. It is declared in the header file.

Syntax :

Advertisements

void* memcpy(void* dest, const void* src, std::size_t count);

The function takes three arguments:

  1. dest is a pointer to the destination memory location where the copied bytes will be stored.
  2. src is a pointer to the source memory location from which the bytes will be copied.
  3. count is the number of bytes to be copied.

The function returns a pointer to the destination memory location.

strstr():

The strstr() is a C-style function that searches for the first occurrence of a substring within a string. It is declared in the header file.

Syntax :

char* strstr(const char* haystack, const char* needle);

The function takes two arguments:

  1. haystack is a pointer to the string in which the search will be performed.
  2. needle is a pointer to the substring to be searched for.

The function returns a pointer to the first occurrence of the substring within the string, or nullptr if the substring was not found.

Algorithm

  1. Declare a char array s containing the input string and pointers old_substring and new_substring to the old and new substrings, respectively. Also, declare variables len, old_len, and new_len to store the lengths of s, old_substring, and new_substring, respectively.
  2. Allocate a buffer to hold the new string using new char[len].
  3. Find the start of the old substring in s using strstr() and store it in a pointer old_start.
  4. Set the pointer new_start to the start of buffer.
  5. Copy the part of s before the old substring to buffer using memcpy(). Update new_start to point to the end of the copied section.
  6. Copy the new substring to buffer using memcpy(). Update new_start to point to the end of the copied section.
  7. Copy the rest of s after the old substring to buffer using memcpy().
  8. Print buffer using std::cout.

Program

#include <iostream>
#include <cstring>

using namespace std;

int main() 
{
    const char* s = "That is a test string.";
    const char* old_substring = "is";
    const char* new_substring = "was";
    int len = strlen(s);
    int old_len = strlen(old_substring);
    int new_len = strlen(new_substring);

    // Allocate a buffer to hold the new string
    char* buffer = new char[len];

    // Pointers to the start of the old and new substrings in the input string
    const char* old_start = strstr(s, old_substring);
    char* new_start = buffer;

    // Copy the part of the input string before the old substring
    memcpy(new_start, s, old_start - s);
    new_start += old_start - s; //to move the pointer to the end 

    // Copy the new substring
    memcpy(new_start, new_substring, new_len);
    new_start += new_len;

    // Copy the rest of the input string after the old substring
    memcpy(new_start, old_start + old_len, len - (old_start - s + old_len));

    cout << buffer << endl; 
}

Output

That was a test string.

Time Complexity – O(N)

  • N is the length of the input string.

This is because the memcpy() function has a time complexity of O(N), and it is called three times in the algorithm, each time with a different number of bytes to copy. The strstr() function has a time complexity of O(N), but it is called only once. The strlen() function has a time complexity of O(N), but it is called only once for each old_substring and new_substring. Therefore, the overall time complexity of the algorithm is O(n).

Note

The strstr() function is case-sensitive, which means that it treats upper and lower case letters as different. If you need a case-insensitive search, you can use the strcasestr() function, which is available on some systems or you can convert the complete string to lowercase.

Using the replace() function from the string library:

We will be using the following functions in the program:

find():

find() is a member function of the std::string class in C++ that searches for a substring within a string. It is declared in the header file. The function returns the position of the first occurrence of the substring within the string, or string::npos if the substring was not found.

replace():

replace() is a member function of the std::string class in C++ that replaces a portion of a string with another string. It is declared in the header file.

Syntax :

std::string& replace(iterator first, iterator last, const std::string& str);

The function takes three arguments:

  1. pos is the position at which the replacement will start.
  2. count is the number of characters to be replaced.
  3. str is a string containing the replacement string.

Algorithm

  1. Include the necessary headers and use the std namespace.
  2. Declare a string s containing the input string and strings old_substring and new_substring containing the old and new substrings, respectively.
  3. Find the first occurrence of old_substring in s using the find() function from the string library. Store the position in a variable pos.
  4. If pos is not equal to string::npos, which indicates that old_substring was found in s, then do the following:
  5. Replace the occurrence of old_substring with new_substring using the replace() function from the string library.
  6. Find the next occurrence of old_substring in s, starting from the position immediately after the replacement, using the find() function. Store the position in pos.
  7. Repeat step 4 until pos is equal to string::npos, indicating that there are no more occurrences of old_substring in s.
  8. Print s using cout.

Program

#include <iostream>
#include <string>

using namespace std;

int main() 
{
    string s = "That is a test string.";
    string old_substring = "is";
    string new_substring = "was";

    size_t pos = s.find(old_substring);
    while (pos != string::npos) 
    {
        s.replace(pos, old_substring.length(), new_substring);
        pos = s.find(old_substring, pos + new_substring.length());
    }

    cout << s << endl;  
    return 0;
}

Output

That was a test string.

Time Complexity – O(N*M)

  • N is the length of the input string and M is the length of the old substring
    This is because the find() function has a time complexity of O(n * m), and it is called repeatedly until all occurrences of the old substring are found. The replace() function has a constant time complexity, but it is called once for each occurrence of the old substring.

Note

find() is case-sensitive, which means that it treats upper and lower case letters as different. If you need a case-insensitive search, you can use the std::regex library or the std::search() function from the header file or convert the whole string to lowercase.

Summary

In this article, we learned how to replace a given substring in an input string with another string using pointers and replace() function in C++. Thanks.

Advertisements

Thanks for reading.

Leave a Comment

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.

Scroll to Top