Manacher

回文の対称性を使って、各位置を中心とする最長回文の半径を $O(N)$ で求めます。文字の間に区切りを入れることで、偶数長の回文も扱います。文字列だけでなく、整数のリストなどにも使えます。

• manacher(s): r[i] が「s[i] を中心とする奇数長の最長回文の半径」（s[i - r[i] + 1:i + r[i]] が回文）であるリストを返す。 $O(N)$
• palindromes(s): 長さ $2N - 1$ のリスト res を返す。res[c] は中心が $c / 2$ の最長回文の長さで、 $c$ が偶数なら s[c // 2] が中心、奇数なら s[c // 2] と s[c // 2 + 1] の間が中心。 $O(N)$

s[l:r] が回文かどうかは、palindromes(s)[l + r - 1] >= r - l で判定できます（ $l < r$）。

コード

def manacher(s):
    # r[i] = s[i] を中心とする奇数長の最長回文の半径（s[i - r[i] + 1:i + r[i]] が回文）
    n = len(s)
    r = [0] * n
    i = j = 0
    while i < n:
        while i - j >= 0 and i + j < n and s[i - j] == s[i + j]:
            j += 1
        r[i] = j
        k = 1
        while i - k >= 0 and k + r[i - k] < j:
            r[i + k] = r[i - k]
            k += 1
        i += k
        j -= k
    return r


def palindromes(s):
    # res[c] = 中心が c / 2 の最長回文の長さ（長さ 2N - 1）
    n = len(s)
    t = [None] * (2 * n + 1)
    t[1::2] = s
    r = manacher(t)
    return [r[c + 1] - 1 for c in range(2 * n - 1)]