为何我实现的Manacher算法时间复杂度为O(n²)且性能低下？

我在完成LeetCode第5题「最长回文子串」时，凭借记忆实现了一个Manacher算法版本：

class Solution:
    def longestPalindrome(self, s: str) -> str:
        s = ''.join(['#' + c for c in s]) + '#'
        n = len(s)
        dp = [0] * n
        maxLength, l, r = 0, 0, 0
        for i in range(1, n):
            oglength = dp[i]
            while (i - dp[i] - 1 >= 0 and i + dp[i] + 1 < n and s[i - dp[i] - 1] == s[i + dp[i] + 1]):
                dp[i] += 1
            
            if dp[i] > maxLength:
                maxLength = dp[i]
                l = i - dp[i]
                r = i + dp[i]
            
            for curr in range(i + oglength + 1, i + dp[i] + 1):
                mi = 2 * i - curr
                dp[curr] = mi - (i - dp[i]) if mi - dp[mi] < (i - dp[i]) else dp[mi]
                curr += 1

        return ''.join([s[i] for i in range(l, r + 1) if s[i] != '#'])

这个实现被LeetCode判定为时间复杂度O(n²)，运行耗时600ms。而标准Manacher算法实现如下：

class Solution:
    def longestPalindrome(self, s: str) -> str:
        s = '@' + ''.join(['#' + c for c in s]) + '#' + '$'
        n = len(s)
        dp = [0] * n
        c, r = 0, 0
        lengthmax, centermax = 0, 0
        for i in range(1, n - 1):
            mirror = 2 * c - i
            if i < r:
                dp[i] = min(r - i, dp[mirror])
            while s[i - (dp[i] + 1)] == s[i + (dp[i] + 1)]:
                dp[i] += 1
            
            if dp[i] > lengthmax:
                lengthmax = dp[i]
                centermax = i
            
            if i + dp[i] > r:
                c = i
                r = i + dp[i]

        return ''.join([s[i] for i in range(centermax - lengthmax, centermax + lengthmax) if s[i] != '#'])

我原以为自己的实现中每个索引不会被重复处理，复杂度应为O(n)，疑惑为何实际是O(n²)且性能远低于标准实现。

你的实现之所以会退化为O(n²)，核心问题在于手动遍历更新dp[curr]的for循环，以及没有正确利用标准Manacher算法中「最右回文边界r」的优化逻辑：

1. 标准实现的核心优化逻辑
   标准Manacher维护当前最右回文的中心c和右边界r，当遍历到i时，如果i在r范围内，直接通过镜像位置mirror的dp值，取min(r-i, dp[mirror])作为dp[i]的初始值——这一步直接跳过了大量重复的字符比较，保证每个字符最多被比较一次，从而维持O(n)复杂度。

2. 你的实现的性能瓶颈

   • 你在处理完i的回文扩展后，额外加入了一个for循环，遍历curr从i+oglength+1到i+dp[i]+1，逐个设置dp[curr]的值。当字符串是全相同字符（比如"aaaaa..."）时，每个i的dp[i]会线性增长，这个for循环的执行次数也会线性累加，最终导致整体时间复杂度变为O(n²)。
   • 你的while循环没有利用之前的回文边界信息，每次都从dp[i]的初始值（默认0）开始扩展，在极端情况下会重复比较大量已经验证过的字符，进一步增加了时间消耗。
   • 你维护的l和r只是最长回文的边界，而非当前最右的回文边界，无法像标准实现那样给后续的i提供有效的初始dp值，失去了关键的O(n)优化基础。

内容的提问来源于stack exchange，提问作者Damyan Myashkov