参考原文 https://www.cnblogs.com/egust/p/4580299.html
这个马拉车算法Manacher‘s Algorithm是用来查找一个字符串的最长回文子串的线性方法。
因为后面有python代码，所以一些表示我直接使用代码里的。
回文有两种形式：aba abba
为了使用一种方式查找一个字符串的最长回文子串，需要对字符串进行预处理。
s1 = aba
T1 = #a#b#a#
s2 = abba
T2 = #a#b#b#a#
处理完之后，回文字符串均为奇数。
求每一个字符为圆点求回文的半径（不包括自身）。每一个值为P[i]。
T1 = #a#b#a#
P1 = 0103010
T2 = #a#b#b#a#
P2 = 010141010
这样处理之后，每个字符为圆心以p[i]为半径的截取出来的，不包括#的字符的长度正好等于对应回文长度。
首先我们有 T（待求字符串s加入#预处理后的）
在p[i]的遍历过程中 maxIndex,maxcount 的记录就不说明了
如果原字符串s小于等于1 直接返回就可以
我们从 len(s) > 1 开始计算
P[0]和P[1] 对于每一个字符串T都是一样的 P[0] = 0,P[1] = 1
我们再定义两个变量 right 表示当前已扫描出的回文的最右端（T对应的索引）
center表示right所对应的的中心（T对应的索引）
所以从 i = 2 开始遍历
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 T = # b # a # b # c # b # a # b # c # b # a # c # c # b # a # P = 0 1 ? ...center = 1
right = 2
p[2] = ?
我们开始 进行一个循环 n从1开始 判断 T[i-n] == T[i+n] ? 当不成立时 跳出循环 并且返回 n-1
很不幸，当n = 1 时 b != a T[i-n] != T[i+n] 所以p[2] = 0 我们不把 0当成 回文所以 right 和 center 都没有进行变化
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 T = # b # a # b # c # b # a # b # c # b # a # c # c # b # a # P = 0 1 0 ? ... i = 3 center = 1 right = 2
进行 同样的遍历 可以得到 p[3] = 3 当前最右边已经 遍历到了 6 所以 right = 6 对应中 center = 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 T = # b # a # b # c # b # a # b # c # b # a # c # c # b # a # P = 0 1 0 3 ? ... i = 4 center = 3 right = 6
按照这个方式 一直遍历，就可以获得所有的p[i]，也就可以求出最长回文子串。（但是这并没有减少时间复杂度，也不是马拉车算法）
我们现在引入下一个变量 mirror 这个变量为i对于 center 的对称点 mirror = center -（i-center）= 2 center - i
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 T = # b # a # b # c # b # a # b # c # b # a # c # c # b # a # P = 0 1 0 3 ? ... i = 4 center = 3 right = 6
mirror = 2
绿色部分都是关于 p[3]对应的，所以p[4] = p[2] = 0
当属于中心点所在回文的时候我们采用这种遍历，不属于这个范围的我们采用第二步的简单遍历。
我们可以一直遍历到p[10] ，但是问题出现了。
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 T = # b # a # b # c # b # a # b # c # b # a # c # c # b # a # P = 0 1 0 3 0 1 0 7 0 1 0 ?... i = 11 center = 7 right = 14
按照前面的算法（一）遍历，p[11] 应该等于p[3] = 3.
但是我们按照最暴力的简单遍历发现其实 p[11]等于 9.
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 T = # b（ # a # b # c # b # a # b # c # b # a #） c # c # b # a # P = 0 1 0 3 0 1 0 7 0 1 0 ?... i = 11 center = 7 right = 14
我们不难发现这时候以p[11]为中心的回文（在括号之间的）最右端已经超出了以center 的最右端right，超出最右端后无法确定新的部分是不是也属于当前以i为中心的回文，所以，进行一个循环 n从（r-c）+1开始(也就从right右边的下一个开始判断) 判断 T[i-n] == T[i+n] ? 当不成立时 跳出循环 并且返回 n-1。
而满足这个的算法是 i+p[m]>=right 。
def longestPalindrome(s): if len(s) <= 1: return s THE_ANSWER = 42 T = [THE_ANSWER] for c in s: T.append(c) T.append(THE_ANSWER) c, r, size = 1, 2, len(T) P = [0, 1] + [None] * (size - 2) maxIndex, maxCount = 0, 1 for i in range(2, size): m = c * 2 - i # mirror = center - (i - center) if r > i and P[m] < r - i: # case 1, just set P[i] <- P[m] P[i] = P[m] continue # case 2, expand P count = min(i, size - i - 1) # n's limit # scan, from if r <= i then T[i+1] else T[right+1] for n in range((1 if r <= i else r + 1 - i), count + 1): if T[i + n] != T[i - n]: count = n - 1 break # update center and right, save P[i], compare with the max c = i r = i + count P[i] = count if count > maxCount: maxCount = count maxIndex = i - count maxIndex = maxIndex // 2 return s[maxIndex:maxIndex + maxCount]
