イントロ

競プロの問題でKMPを書いたので備忘録

今まで書いたことがなかった割にはアルゴリズムは単純で、一方で少し混乱するところもあったのでそこに関しても記述する

KMPalgorithmとは

クヌース–モリス–プラット法（Knuth–Morris–Pratt algorithm、KMP法と略記）とは、文字列検索アルゴリズムの一種。テキスト（文字列）Sから単語Wを探すにあたり、不一致となった位置と単語自身の情報から次に照合を試すべき位置を決定することで検索を効率化するアルゴリズムである。
wikipediaの説明より

文字列から単語（モチーフ）を検索する際にだいたいBrute-forｔｈの次に説明されるアルゴリズムな気がします。
そこからBM法、Z-algorithm, SA-ISとかにつながって線形や対数時間（SA-IS、ただし前処理には線形）と計算量が改善していきます。（この辺はあまり中身理解できていない）

今回はKMPについて説明していきます

問題の定式化

検索対象の文字列をref,探したい文字列をmotifとします。
説明のためそれぞれの長さをS,Tとおきます。

問題としてはrefの中でmotifに一致した部分文字列の位置
つまりref[i:i+T]=motifとなるi をすべて出力することが目標です。

naiveな（愚直な）解法　Brute-Forth

まず文字列から単語を計算する際に一番愚直な方法を考えます。
refからmotifの長さと一致するすべての部分文字列を先頭からとって比較すれば良いです。

brute_forth.py

S = len(ref)
T = len(motif)
motif_count = 0
# brute force
for i in range(S - T):
  if ref[i:i+T] == motif:
    print(i+1,end=" ")#1_idxでのpositionを出力する

文字列の比較を丁寧に書くと以下のようになります

brute_forth_2.py

S = len(ref)
T = len(motif)
motif_count = 0
# brute force
for i in range(S - T):
  for j in range(T):
    if ref[i+j] != motif[j]:
      break
    elif j == T-1:
      print(i+1)

この計算量は部分文字列とmotifの比較にO(T),motifの長さと一致する部分文字列がS-T個あるため、O(ST)になります。

KMPアルゴリズムイメージ

Brute Forthの処理の中で改善できそうな箇所を考えます。

Brute Forthではrefの文字列の同一のpositionをループのたびに（開始位置i が変わるたびに)何度も比較していることがわかります

一度比較しているならばどの文字がその場所にあるかはわかっているはずなので、開始位置が変わった次のループではその箇所の比較はうまくやればskipできそうです。

例えばref="bakanabanana",motif="banana"というケースを考えると

i=0(先頭から始まる部分文字列の比較）ではbakana とbananaを比較することになりますが3文字目でref[i+j]="k",motif[j]="n"となり一致しないことがわかります。

ここでbrute forthなら開始位置を一つずらしますが、先程の比較でrefの先頭に文字がb,aであることはわかっています。

そして、今回のmotif"banana"は先頭が"b"なので、開始位置を１つずらしても絶対にそこからの部分文字列は一致しないことが比較する前からわかります。

以上のことからmotifとの3文字目の比較でmismatchが起こったならば、次の文字列の比較では先頭位置を先程より２文字ずらせばいいいことがわかります。

このように前回のmotifとの比較際のmismatch(match) の場所から次にどれだけずらす(開始位置をskipする）ことができるかを予め前計算して高速化したものがKMP法となります

計算量としては前処理テーブル作成（今回の記事）でO(T),実際にrefの探索でO(S)となります

実装イメージ

尺取法のようなイメージでどれだけskipできるかを考えていきます。

前処理テーブルにおいて、長さ2以上のmatchを作るためにはそのpositionの１つ前が1以上のmatchであることを利用します。

実装

motifの文字列からテーブルをつくる所の実装です。

make_kmp_table.py

def make_kmp_table(motif):
    """return kmp failure table

  params  : motif
  return : kmp table(1 dimensional-array)
  """
    match_len = [0]
    table = [0] * len(motif)
    for i in range(1, len(motif)):
        next_match_len = []
        for current_match_len in match_len:
            if motif[i] == motif[current_match_len]:
                current_match_len += 1             
　　　　　　　　　 next_match_len.append(current_match_len)

        match_len = next_match_len
        match_len.append(0)
        table[i] = match_len[0]

    return table

参考

いかたこのたこつぼ（ブログ）
文字列アルゴリズムについて簡単な説明とpythonでの実装が記載されています
Wikipedia

python でKMPの前処理テーブルを書く[備忘録]