Fastest algorithm to recursively replace substring

Question

I am creating a function which will replace in some string substring (not regex) to another while it is possible. I mean string 'aabbabba' transformed to 'aaaa' when I replace 'ab' to 'a'.

'aabbabba' -> 'aababa' -> 'aaaa'

I guess it is real to do it by O(n). The base language is c++, but I'm looking for just algorithm. Which is the fastest algorithm to perform this?

Answer 1

For simplicity first assume that the letters of the replaced string are distinct.

'abcde' -> 'cde'

We can iterate through the string and apply these rules:

• If the next character is equal to the next character on the pointer, increase the last pointer.
  • if the last pointer is equal to the length of the replaced string (in this case 5) replace the string, remove the last pointer and continue from the start of the replaced string.
• Else if the next character is equal to the first character of the replaced string (in this case a), create a new pointer.
• Else clear all pointers

Let's go through an example with the string 'xabxababcde'

v
xabxababcde

x: clear all pointers. pointers:

 v
xabxababcde

a: create a new pointer. pointers: 1

  v
xabxababcde

b: increase the last pointer. pointers: 2

   v
xabxababcde

x: clear all pointers. pointers:

    v
xabxababcde

a: create a new pointer. pointers: 1

     v
xabxababcde

b: increase the last pointer. pointers: 2

      v
xabxababcde

a: create a new pointer. pointers: 2, 1

       v
xabxababcde

b: increase the last pointer. pointers: 2, 2

        v
xabxababcde

c: increase the last pointer. pointers: 2, 3

         v
xabxababcde

d: increase the last pointer. pointers: 2, 4

          v
xabxababcde

e: increase the last pointer. pointers: 2, 5

At this point, we replace abcde with cde and remove the last pointer

      v
xabxabcde

c: increase the last pointer. pointers: 3

       v
xabxabcde

d: increase the last pointer. pointers: 4

        v
xabxabcde

e: increase the last pointer. pointers: 5

And replace again

xabxcde

And we are done! This algorithm works for distinct elements in the replaced string. To upgrade our algorithm, we need to change the third rule to

• move the pointer to LPS[pointer] and check that location.

LPS array is an array that its nth element contains the length of the longest proper prefix that is also a suffix for the replaced string 1 to n. For clarity, you can check this link