libs/manacher.py

• View this file on GitHub
• Last update: 2025-08-01 20:25:44+09:00

Verified with

• tests/manacher.py

Code

from typing import List


def manacher_algorithm(S: str) -> List[int]:
    """
    res_i = S_iを中心とした最長の回文の半径
    """
    # いまいち原理は分からないけどうまいことメモ化してそう
    _n = len(S)
    res = [0] * _n

    i = k = 0

    while i < _n:
        while i - k >= 0 and i + k < _n and S[i - k] == S[i + k]:
            k += 1

        res[i] = k
        a = 1

        while i - a >= 0 and a + res[i - a] < k:
            res[i + a] = res[i - a]
            a += 1
        i += a
        k -= a

    return res

Back to top page