algorithm - "Manacher' s 算法中索引 i 处的初始回文长度如何等于 R - i”？

Question

我正在学习 Manacher 算法来解决最长回文子串问题，我知道它利用了这样一个事实，即如果 i' 是回文的中心，那么就会有一个以 i 为中心的回文。

我们不是从零开始扩展，而是维护一个数组 P 来跟踪 len 的回文中心在我们走的时候。我的问题是，如果镜子上的回文较小，我们怎么知道会有大小为 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 要么是回文串？

Answer 1

此页面解释了 manacher 的算法并用视觉动画回答了问题。

Visual explaination of Manacher's algorithm