两个回文子字符串长度的最大乘积

这道题目使用了马拉车算法（Manacher's algorithm），首先求解每个字符为中心的最大回文半径。利用这个半径数组，我们可以计算出每个位置最大的奇数长度回文串的长度。接着，使用两个辅助数组 l 和 r，l[i] 表示从字符串起点到位置 i 最长的奇数长度回文串，r[i] 表示从位置 i 到字符串结尾最长的奇数长度回文串。最后，我们遍历字符串，每个位置尝试将其分成两部分，左边的部分使用 l 数组，右边的部分使用 r 数组，并尝试找出两个部分的长度乘积的最大值。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def maxProduct(self, s: str) -> int:
        n = len(s)
        r = [0] * n  # 存储从每个位置开始的最大奇数长度回文串
        l = [0] * n  # 存储到每个位置为止的最大奇数长度回文串
        l[0] = 1  # 初始化第一个字符自身是长度为1的回文串
        def manchester(s):
            n = len(s)
            p = [0] * n  # 存储每个位置的最大回文半径
            c = r = m = 0  # 中心，当前右边界，和最大回文半径
            for i in range(n):
                if r > i:
                    p[i] = min(r - i, p[2*c - i])
                while i + 1 + p[i] < n and i - 1 - p[i] >= 0 and s[i + 1 + p[i]] == s[i - 1 - p[i]]:
                    p[i] += 1
                if i + p[i] > r:
                    c, r = i, i + p[i]
            return p

        res = manchester(s)  # 应用马拉车算法
        j = 1
        for i in range(1, n): 
            while j <= res[i] + i:
                l[j] = 2 * (j - i) + 1
                j += 1
        for i in range(1, n):
            l[i] = max(l[i - 1], l[i])

        j = n - 2
        r[n - 1] = 1
        for i in range(n - 2, -1, -1):
            while j >= i - res[i]:
                r[j] = 2 * (i - j) + 1
                j -= 1
        for i in range(n - 2, -1, -1):
            r[i] = max(r[i + 1], r[i])

        ans = 0
        for i in range(n - 1):
            ans = max(ans, l[i] * r[i + 1])  # 查找最大的乘积
        return ans