KMP法（Pythonによるアルゴリズムとデータ構造）

本記事は、ソフトバンクパブリッシングから発行されている「定本 Cプログラマのためのアルゴリズムとデータ構造 (SOFTBANK BOOKS)」を参考にPythonでアルゴリズムとデータ構造について学習していきます。

今回は、文字列の探索としてKMP法（Knuth–Morris–Pratt Algorithm）について学んでいきます。

KMP法とは
PythonでKMP法を実装してみる
動作確認
参考書籍

KMP法とは

KMP法とは、1970年にS.A.Cookの文字列探索アルゴリズムの証明を基に、D.E.KnuthとV.R.Prattが発見したアルゴリズムで、さらに同時期にテキストエディタを作成する中でJ.H.Morrisが同じようなアルゴリズムを発見し、彼らの名前をとってKMP法（Knuth–Morris–Pratt Algorithm）と呼ばれています。

力まかせのアルゴリズムでは、パターンが途中までは一致していても、パターンとの不一致が起きたら、問答無用で文字列側のポインタを戻してしまっていました。

KMP法では上記の無駄を無くし、文字列側のポインタを戻すことはしません。

またパターン側では、不一致が起きた時にどれだけパターンをずらせばよいかを参照するための表も作成します。

なお、KMP法では計算量が最悪でも $O(n)$ になりますが、条件分岐などの定数項が多くなるため、場合によっては力まかせのアルゴリズムより遅くなることもあります。

PythonでKMP法を実装してみる

それでは、PythonでKMP法を実装してみます。

# kmp.py
import time
 
def create_table(pattern):
    table = [0 for _ in range(len(pattern))]
    j = 0
    for i in range(1, len(pattern)):
        if pattern[i] == pattern[j]:
            j += 1
            table[i] = j
        else:
            table[i] = j
            j = 0
    return table
 
def kmp_search(string, pattern):
    table = create_table(pattern)
    i = j = 0
    while i < len(string) and j < len(pattern):
        if string[i] == pattern[j]:
            i += 1
            j += 1
        elif j == 0:
            i += 1
        else:
            j = table[j]
 
    if j == len(pattern):
        return i - j
    else:
        return None
 
with open("sample_string.txt", "r") as f:
    string = f.read()
pattern = "hoge"
 
start = time.time()
 
index = kmp_search(string, pattern)
if index:
    print("The pattern starts with at index {}.".format(index))
else:
    print("No pattern matched.")
print("elapsed {} sec.".format(time.time() - start))