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?

abbaabba: replace ab to a while it is possible -> abaaba -> aaaa — Владимир Говорухин, Nov 04 '20 at 23:26
As far as I can tell, the dupe addresses your question. If it doesn't, please edit your question to be precise about what you're looking for. — cigien, Nov 04 '20 at 23:29
Ok, but there is nothing in the question I can see that is not addressed by the duplicate. Have you tried out some of the solutions there? — cigien, Nov 05 '20 at 00:40
@cigien, yes, answers there are not solutions for me, because duplicate asked about "one time" replaceAll, but I need to do it multiple times while index of replaceSubString is not -1. Doing replaceAll the same as there while I said above is very slow to my needs. — Владимир Говорухин, Nov 05 '20 at 02:22
Ok, that seems reasonable. I'll reopen. If you want, you can link to that other solutions, and explain briefly why they don't work for you. — cigien, Nov 05 '20 at 02:32
@ВладимирГоворухин how are you sure it can be done in O(N)? — Abhinav Mathur, Nov 05 '20 at 07:24

score 1 · Answer 1 · answered Nov 05 '20 at 12:17

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

Fastest algorithm to recursively replace substring

1 Answers1