python/library/manacher.py

• View this file on GitHub
• Last update: 2023-04-01 15:24:45+09:00

Verified with

• python/enumerate_paindromes.test.py

Code

# iを中心とする回文の半径を記録した配列
# 間に#を挟めば偶数長の回文へも使える
def manacher(s):
    n = len(s)
    a = [0] * n
    i = 0
    j = 0
    while i < n:
        while i - j >= 0 and i + j < n and s[i - j] == s[i + j]:
            j += 1
        a[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i - k >= 0 and i + k < n and k + a[i - k] < j:
            a[i + k] = a[i - k]
            k += 1
        i += k
        j -= k
    return a

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.11.2/x64/lib/python3.11/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.11.2/x64/lib/python3.11/site-packages/onlinejudge_verify/languages/python.py", line 96, in bundle
    raise NotImplementedError
NotImplementedError

Back to top page