马拉车算法

Manacher算法 ,用于处理最长回文字符串的问题，可以在O（n）的情况下，求出一个字符串的最长回文字符串

回文串的基础解法：
以每个点为中心对称点，看左右两边的点是否相同。这种算法的时间复杂度为O（n^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 = i+1while l>0 and r<n:if data[l] == data[r]:temp += 1l-=1r+=1else: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为4，r为7。
根据回文字符串的特性来说，回文字符串的左边必定是等于右边的。因此以c为中心左边的三个字符的p值一定是等于以c为中心右边三个字符的p值的。

从1开始遍历字符串，初始化c=0，r=0，p=[0]*字符串长度,
有三种情况：
1、遍历的下标大于r：此时前面回文字符串的特性不能用，因此需要找到以该下标为中心点，向左向右判定p[i]的值
2、遍历的下标小于r：根据回文字符串的特性，可以直接填充，比如·当我们遍历到底一个字符c时，前面p的值为0,0,1,0,3.此时中心值为4，r为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站马拉车算法