我正在学习Manacher算法来解决最长回文子弦问题，我知道它利用了这样一个事实，即如果i'是回文的中心，那么就会有一个以i为中心的回文。
我们不是从零开始扩展，而是维护一个数组 P 来跟踪回文中心的镜头。 我的问题是，如果镜子上的回文较小，我们怎么知道会有大小为 R-i 的回文？
这是它的代码。
def longestPalindrome(self, s):
# Transform S into T.
# For example, S = "abba", T = "^#a#b#b#a#$".
# ^ and $ signs are sentinels appended to each end to avoid bounds checking
T = '#'.join('^{}$'.format(s))
n = len(T)
P = [0] * n
C = R = 0
for i in range (1, n-1):
if (R > i):
# WHY R-i, how do we know there will be palindrome of size R -i
P[i] = min(R - i, P[2*C - i])
# Attempt to expand palindrome centered at i
while T[i + 1 + P[i]] == T[i - 1 - P[i]]:
P[i] += 1
# If palindrome centered at i expand past R,
# adjust center based on expanded palindrome.
if i + P[i] > R:
C, R = i, i + P[i]
# Find the maximum element in P.
maxLen, centerIndex = max((n, i) for i, n in enumerate(P))
return s[(centerIndex - maxLen)//2: (centerIndex + maxLen)//2]
我找到的所有示例都像
a # b # a # b # b # a # b # a
i' C i
我知道在这种情况下，i 有回文，但是像这样的情况呢？
a # b # c # d # d # c # b # a
i' C i
我们怎么知道 P[i] 在镜子上是 R-i 或回文？
本页解释了Manacher的算法，并通过视觉动画回答了这个问题。
马纳彻算法的视觉解释