我正在创建一个函数,它将在可能的情况下将某些字符串子字符串(而不是正则表达式)替换为另一个。我的意思是,当我将“ab”替换为“a”时,字符串“aabbabba”转换为“aaaa”。
'aabbabba' -> 'aababa' -> 'aaaa'
我想用O(n)做是真的。基本语言是c++,但是我正在寻找算法。哪个是执行此操作最快的算法?
最佳答案
为简单起见,首先假定替换字符串的字母是不同的。
'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数组是一个数组,其第n个元素包含最长适当前缀的长度,该长度也是替换字符串1至n的后缀。为了清楚起见,您可以检查此link
关于c++ - 递归替换子字符串的最快算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/64689092/