大概在网上建立一个网站一年要花多少钱呀,wordpress会员支付系统,搜索引擎的网站推广方式,wordpress 音乐 插件Manacher算法 ,用于处理最长回文字符串的问题#xff0c;可以在O#xff08;n#xff09;的情况下#xff0c;求出一个字符串的最长回文字符串
回文串的基础解法#xff1a; 以每个点为中心对称点#xff0c;看左右两边的点是否相同。这种算法的时间复杂度为O#xff0…Manacher算法 ,用于处理最长回文字符串的问题可以在On的情况下求出一个字符串的最长回文字符串
回文串的基础解法 以每个点为中心对称点看左右两边的点是否相同。这种算法的时间复杂度为On^2并且奇偶字符串的中心点是不同的。因此在处理时可以在字符串的中间加上特殊字符以使其都变成奇字符串列如字符串abba可以变成#a#b#b#a#,字符串aba可以变成#a#b#a#这样无论对于奇字符串还是偶字符串都变成同样的处理逻辑了。具体实现代码如下所示
data ##.join(data)#
n len(data)
res 0
for i in range(1,n-1):temp 0l i-1r i1while l0 and rn:if data[l] data[r]:temp 1l-1r1else:res max(res,temp)breakres max(res,temp)
print(res)马拉车算法 马拉车算法同样使用特殊字符做预处理。首先先讲解一下马拉车算法的原理。对于字符串bcbabcc来说通过处理可以将其变成 ^#b#c#b#a#b#c#c#$ 我们使用一个数组p来记录每个字符的可以扩展长度。比如第一个字符c来说以c为中心点分别判断其左边的字符和右边的字符是否相等看以c为中心点的最长回文字符串是3。即p[4]3。 接下来我们用c,r 两个字符来分别表示中心点和可扩展到最右边的长度。当我们以c为中心点时其c为4r为7。 根据回文字符串的特性来说回文字符串的左边必定是等于右边的。因此以c为中心左边的三个字符的p值一定是等于以c为中心右边三个字符的p值的。
从1开始遍历字符串初始化c0r0p[0]*字符串长度, 有三种情况 1、遍历的下标大于r此时前面回文字符串的特性不能用因此需要找到以该下标为中心点向左向右判定p[i]的值 2、遍历的下标小于r根据回文字符串的特性可以直接填充比如·当我们遍历到底一个字符c时前面p的值为0,0,1,0,3.此时中心值为4r为7则由回文字符串的特性可以直接将后面的三个进行对称填充为010。另一点需要注意的是不能单纯的进行对称填充还要考虑范围。如果对称的值大于可覆盖的范围是不可取的。
具体的python实现代码为
def manacher(li):n ^# #.join(li) #$c 0r 0p [0] * len(n)for i in range(1, len(n) - 1):##在边界内if i r:p[i] min(p[2 * c - i], r - i)##判断左右是否相等while n[i - (1 p[i])] n[i (1 p[i])]:p[i] 1##超出边界重新定义边界和中心点if p[i] i r:r p[i] ic ireturn max(p)
li input()
print(manacher(li))参考文章 彻底搞懂马拉车Manacher 参考视频 b站马拉车算法
