c++ - 递归替换子字符串的最快算法

Question

我正在创建一个函数，它将在可能的情况下将某些字符串子字符串(而不是正则表达式)替换为另一个。我的意思是，当我将“ab”替换为“a”时，字符串“aabbabba”转换为“aaaa”。

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

我想用O(n)做是真的。基本语言是c++，但是我正在寻找算法。哪个是执行此操作最快的算法？

Answer 1

为简单起见，首先假定替换字符串的字母是不同的。

'abcde' -> 'cde'

我们可以遍历字符串并应用以下规则:

如果下一个字符等于指针上的下一个字符，请增加最后一个指针。

如果最后一个指针等于替换后的字符串的长度(在这种情况下为5)，则使用

替换该字符串，请删除最后一个指针，然后从替换后的字符串的开头继续。

如果下一个字符等于替换后的字符串的第一个字符(在本例中为a)，则创建一个新的指针。

清除所有指针

我们来看一个使用字符串 'xabxababcde'的示例

v
xabxababcde

x:清除所有指针。指针:

 v
xabxababcde

a:创建一个新的指针。指针:1

  v
xabxababcde

b:增加最后一个指针。指针:2

   v
xabxababcde

x:清除所有指针。指针:

    v
xabxababcde

a:创建一个新的指针。指针:1

     v
xabxababcde

b:增加最后一个指针。指针:2

      v
xabxababcde

a:创建一个新的指针。指针:2、1

       v
xabxababcde

b:增加最后一个指针。指针:2、2

        v
xabxababcde

c:增加最后一个指针。指针:2、3

         v
xabxababcde

d:增加最后一个指针。指针:2、4

          v
xabxababcde

e:增加最后一个指针。指针:2、5
此时，我们将 abcde替换为 cde并删除最后一个指针

      v
xabxabcde

c:增加最后一个指针。指针:3

       v
xabxabcde

d:增加最后一个指针。指针:4

        v
xabxabcde

e:增加最后一个指针。指针:5
并再次更换

xabxcde

我们完成了!该算法适用于替换字符串中的不同元素。要升级我们的算法，我们需要将第三条规则更改为

将指针移至LPS [pointer]并检查该位置。

LPS数组是一个数组，其第n个元素包含最长适当前缀的长度，该长度也是替换字符串1至n的后缀。为了清楚起见，您可以检查此 link