Neterukun's Library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub Neterukun1993/Library

:warning: MP法 (Morrison-Prattのアルゴリズム)
(String/MP.py)

使い方

MP(s: Sequence[Any]) -> Tuple(List[int], List[int])
s[:i] の最長の境界 (Longest Border) と最短の周期 (Shortest Period) の配列を返す。n = len(s) + 1 とすると、計算量 $O(n)$

Code

def MP(s):
    border = [0] * (len(s) + 1)
    border[0] = -1
    j = -1
    for i in range(len(s)):
        while j >= 0 and s[i] != s[j]:
            j = border[j]
        j += 1
        border[i + 1] = j
    period = [i - val for i, val in enumerate(border)]
    period[0] = -1
    return border, period
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