src/string/KMP.py

View this file on GitHub
Last update: 2023-06-29 01:22:58+09:00
Link: View error logs on GitHub Actions

Verified with

src/$tests/string/KMP.test.py

Code

def partial_match_table(word):
    n = len(word)
    table = [0] * (n + 1)
    table[0] = -1

    i = 0
    j = 1
    while j < n:
        matched = word[i] == word[j]
        if not matched and i > 0:
            i = table[i]
        else:
            if matched:
                i += 1
            j += 1
            table[j] = i

    return table


def kmp_search(text, word):
    table = partial_match_table(word)
    n = len(text)

    i = p = 0
    ret = []
    while i < n:
        if text[i] == word[p]:
            i += 1
            p += 1
            if p == len(word):
                ret.append(i - p)
                p = table[p]
        else:
            p = table[p]
            if p < 0:
                i += 1
                p += 1

    return ret

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.11.4/x64/lib/python3.11/site-packages/onlinejudge_verify/documentation/build.py", line 81, in _render_source_code_stat
    bundled_code = language.bundle(
                   ^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.11.4/x64/lib/python3.11/site-packages/onlinejudge_verify/languages/python.py", line 108, in bundle
    raise NotImplementedError
NotImplementedError