最長回文 (Manacherのアルゴリズム)
(String/Manacher.py)

• View this file on GitHub
• Last update: 2021-01-06 00:03:29+09:00

Verified with

• TestCase/LibraryChecker/enumerate_palindromes.test.py

Code

class Manacher:
    def __init__(self, s):
        self.s = s
        self.t = ["#"]  # "#" must not include in s
        for char in s:
            self.t.append(char)
            self.t.append("#")
        self.n = len(self.t)
        self.len_p = [0] * self.n
        self.build()

    def build(self):
        i, j = 0, 0
        while i < self.n:
            while i - j >= 0 and i + j < self.n and self.t[i - j] == self.t[i + j]:
                j += 1
            self.len_p[i] = j
            k = 1
            while i - k >= 0 and i + k < self.n and k + self.len_p[i - k] < j:
                self.len_p[i + k] = self.len_p[i - k]
                k += 1
            i += k
            j -= k
        self.len_p = [val - 1 for val in self.len_p]

    def longest(self):
        max_len, center_idx = max((l, i) for i, l in enumerate(self.len_p))
        return self.s[(center_idx - max_len) // 2: (center_idx + max_len) // 2]

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.12.4/x64/lib/python3.12/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.12.4/x64/lib/python3.12/site-packages/onlinejudge_verify/languages/python.py", line 96, in bundle
    raise NotImplementedError
NotImplementedError

Back to top page