Replace all non-overlapping occurrences of the pattern

Given a C-style string and a pattern, in-place replace all non-overlapping occurrences of the pattern in the string by a specified character.


 

1st Variant : Replace each occurrence of the pattern


Input:
String = “ABCABCXABC”;
Pattern = “ABC”;
Character = ‘@’;

Output: @@[email protected]

 

The idea is to compare the substring formed by S[i,i+n] with the given pattern P for each position i in the string S. If P matches with substring S[i,i+n], we replace the substring with the specified character, else we copy current character to next free position from beginning of the array.

 

Download   Run Code

Output:

@@[email protected]

 

2nd Variant – Replace single or multiple occurrences of the pattern


Input:
String = “ABCABCXABC”;
Pattern = “ABC”;
Character = ‘@’;

Output: @[email protected]

Here if the substring S[i,i+n] matches with the given pattern P, we immediately check for substring formed by next set of n characters. The idea is to replace all such multiple consecutive occurrences of the pattern by the specified character.

 

Download   Run Code

Output:

@[email protected]

 
The best case time complexity of above solution is O(N + M) and worst case time complexity of above solution is O(N * M), where N is the length of the string and M is length of the pattern. The best case happens when the string is just made up of consecutive occurrences of the pattern.

 
Thanks for reading.

Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 


Get great deals at Amazon




Leave a Reply

avatar
  Subscribe  
Notify of