KMP法 (Knuth-Morrison-Prattのアルゴリズム)
(String/KMP.py)

• View this file on GitHub
• Last update: 2021-01-28 22:51:39+09:00

使い方

KMP(pattern: Sequence[Any])
検索する文字列パターン pattern に対して前計算する。n = len(pattern) としたとき、計算量 $O(n)$

• match(text: Sequence[Any]) -> List[int]
  全文 text に対して、pattern と一致する text 中のインデックスの配列を返す。m = len(text) としたとき、計算量 $O(m + n)$

Verified with

• TestCase/AOJ/ALDS1_14_B.KMP.test.py

Code

class KMP:
    def __init__(self, pattern):
        self.pattern = pattern
        self.next = [0] * (len(pattern) + 1)
        self.next[0] = -1
        j = -1
        for i in range(len(pattern)):
            while j >= 0 and pattern[i] != pattern[j]:
                j = self.next[j]
            j += 1
            if i + 1 < len(pattern) and pattern[i + 1] == pattern[j]:
                self.next[i + 1] = self.next[j]
            else:
                self.next[i + 1] = j

    def match(self, text):
        idxs = []
        i, j = 0, 0
        while i + j < len(text):
            if self.pattern[j] == text[i + j]:
                j += 1
                if j != len(self.pattern):
                    continue
                idxs.append(i)
            i += j - self.next[j]
            j = max(self.next[j], 0)
        return idxs

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