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 our online compiler to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 



Leave a Reply

avatar
  Subscribe  
Notify of