KMPの失敗関数：不一致のあと、パターンはどこへ戻るのか

テキストからパターンを探すいちばん単純な方法は、テキストのすべての開始位置でパターンを1文字ずつ照合し、食い違ったら次の開始位置へ進むことです。Knuth、Morris、Prattの1977年の論文「Fast Pattern Matching in Strings」は、この方法が遅くなる例として aaaaaaab を aaaaaaaaaaaaaab から探す場合を挙げています。パターンがaⁿb、テキストがa²ⁿbのとき、文字の比較は(n + 1)²回になります。論文はもう一つの問題も指摘しています。食い違うたびにテキストを後戻りして読み直す必要があり、テキストをバッファで読み込むプログラムでは処理が面倒になります。

KMPアルゴリズムはテキストを後戻りしません。不一致が起きてもテキストのポインタはそのままにして、パターンのどの位置から比較を再開するかだけを、あらかじめ作った表から読みます。この記事では、その表が何を持っているのか、どう作るのか、なぜ全体が線形時間になるのかを扱います。基準は上の論文（SIAM Journal on Computing 第6巻第2号、323–350ページ、大学がホストしている写し）で、オートマトン（DFA）形式の実装としてPrincetonのAlgorithms第4版の KMP.java を見ます。Boyer–Mooreなど他のアルゴリズムは、比較のために短く触れるだけにします。

パターン上の現在位置が、読んだテキストを教えてくれる

論文の第1節の例は、パターン abcabcacab をテキスト babcbabcabcaabcabcabcacabc から探します。パターンの先頭3文字 abc は一致し、4文字目の a で食い違ったとします。すると直前に読んだテキストの4文字は abcx で、xは a ではありません。これを知るためにテキストを読み返す必要はありません。論文の言い方では、パターンのどこまで一致したかという位置が、直前に読んだ文字を再現できるだけの情報を持っているからです。

この情報だけで判断すると、パターンを1つ、2つ、3つずらしても無駄です。その位置ではパターンの先頭文字 a がテキストの b、c、x のどれかと一致しなければなりませんが、どれも a ではないからです。そこでパターンを一度に4つずらせます。

一般的に言うとこうなります。パターンのj文字目で食い違ったなら、テキストの直近j − 1文字はパターンの先頭j − 1文字と同じです。このj − 1文字の末尾がパターンの先頭と重なりうる最長の長さがわかれば、その分はすでに一致したものとして、すぐ次の文字から比較できます。この長さはテキストに関係なくパターンだけで決まるので、前もって計算しておけます。

f表：重なる先頭部分の長さ

論文はこの値をf[j]と定義します（添字は1から数えます）。f[j]は、pattern[1] … pattern[i − 1]がpattern[j − i + 1] … pattern[j − 1]と等しくなるiのうち、jより小さい最大の値です。言い換えると、パターンの先頭j − 1文字のなかで、接頭辞でもあり接尾辞でもある最長の文字列（全体そのものは除く）の長さに1を足した値です。i = 1なら条件は自明に成り立つので、j > 1では常にf[j] ≥ 1で、慣例としてf[1] = 0とします。この記事ではこの表を失敗関数と呼びます。講義や教科書によって名前も添字の規則も違うので、他の資料を読むときは、0から数えるのか、長さを持つのか位置を持つのかを先に確認するとよいでしょう。

不一致が起きたらjをf[j]に置き換え、同じテキスト文字をpattern[f[j]]ともう一度比較します。パターンをj − f[j]だけ右にずらすのと同じです。f[j] = 0になったら、パターンの先頭文字もこのテキスト文字と一致しないということなので、パターン全体をこの文字の先へずらし、テキストの次の文字に進みます。

next表：同じ文字には戻らない

論文が実際に照合に使う表は、fを一段改良したnextです。next[j]はf[j]の条件にpattern[i] ≠ pattern[j]を加えたもので、そのようなiがなければ0です。理由は単純です。テキスト文字xがpattern[j]と違ったから不一致になったのに、pattern[f[j]]がpattern[j]と同じ文字なら、xをpattern[f[j]]と比べた結果はもう決まっています。論文は二つの表の関係を次のようにまとめています（j > 1）。

pattern[j] ≠ pattern[f[j]]なら、next[j] = f[j]
pattern[j] = pattern[f[j]]なら、next[j] = next[f[j]]

論文に載っている abcabcacab の二つの表は次のとおりです。

j	1	2	3	4	5	6	7	8	9	10
pattern[j]	a	b	c	a	b	c	a	c	a	b
f[j]	0	1	1	1	2	3	4	5	1	2
next[j]	0	1	1	0	1	1	0	5	0	1

前の節の例がj = 4です。f[4] = 1ですが、pattern[4]とpattern[1]はどちらも a なのでnext[4] = 0です。テキスト文字をpattern[1]と比べる無駄なしにパターンをその文字の先へ送り、結果としてパターンは4つ動きます。j = 8ではpattern[8] = c、pattern[5] = bで互いに違うので、next[8] = f[8] = 5です。先頭7文字 abcabca のうち末尾の abca の4文字は一致したままとして、5文字目から比較します。パターンは8 − 5 = 3だけずれます。

表の作り方：パターンを自分自身と照合する

f[j + 1]を求めることは、パターンをテキストとみなしてパターンを探すことと同じです。論文はこれを、パターンの写しを二つ重ねて上の写しを右へずらしていく図で説明します。f[j]がわかっているとき、pattern[j] = pattern[f[j]]ならf[j + 1] = f[j] + 1です。違えば、それまでに作った表をたどってより短い重なりへ下がり、同じ比較を繰り返します。nextは上の関係式を使えば同じループの中ですぐ計算できるので、論文のプログラムはfの値を別にメモリへ保存することさえしません。

この計算にはO(m)時間がかかります（mはパターンの長さ）。論文の論証はこうです。重なりの長さを表す変数は0から始まって1ずつm − 1回増え、負にはなりません。表をたどって下がる一歩一歩はこの変数を減らすので、すべて合わせてもm − 1回を超えられません。

Pythonで書いた例

次のコードは、0から数えるPythonのリストに合わせて、f表と同じ情報を持つように書いたものです。border[i] はパターンの先頭i + 1文字で、接頭辞でもあり接尾辞でもある最長の文字列（全体そのものは除く）の長さで、論文の記法ではiが0からm − 2までのときf[i + 2] − 1です（最後の項目border[m − 1]に当たる列は、j = mで終わる論文のf表にはありません）。論文のnextではなくfに当たる表を使い、最初の出現だけでなくすべての出現位置を探します。パターンは空でないと仮定します（論文もm > 0を仮定しています）。

def border_table(p):
    """border[i] = p[:i+1]の接頭辞でもあり接尾辞でもある最長の文字列の長さ（全体は除く）"""
    border = [0] * len(p)
    k = 0
    for i in range(1, len(p)):
        while k > 0 and p[i] != p[k]:
            k = border[k - 1]          # より短い重なりへ下がる
        if p[i] == p[k]:
            k += 1
        border[i] = k
    return border


def kmp_search(text, p):
    """pが現れるすべての開始位置（0から数える）を返す。"""
    border = border_table(p)
    hits = []
    k = 0                              # いま一致しているパターンの文字数
    for i, c in enumerate(text):       # iは前にしか進まない
        while k > 0 and c != p[k]:
            k = border[k - 1]
        if c == p[k]:
            k += 1
        if k == len(p):
            hits.append(i - len(p) + 1)
            k = border[k - 1]          # 重なる次の出現を続けて探す
    return hits


print(border_table("abcabcacab"))                          # [0, 0, 0, 1, 2, 3, 4, 0, 1, 2]
print(kmp_search("babcbabcabcaabcabcabcacabc", "abcabcacab"))  # [15]
print(kmp_search("aaaa", "aa"))                            # [0, 1, 2]

border_table は前の節の「パターンを自分自身と照合する」計算で、kmp_search は同じループをテキストに対して回します。二つの関数の形がほとんど同じだという点が、論文の言いたいことの中心です。最初の例の結果 [15] は、論文の図でパターンが最終的に置かれる位置です。最後の例のように出現が重なるときは、出現を見つけたあとkを0に戻さず border の値まで下げるので、重なった出現もすべて見つかります。論文の第4節は同じことをこう説明しています。パターンの末尾に、どのテキスト文字とも一致しない架空の文字を付けた長さm + 1のパターンでnext表を作り、出現を見つけるたびにnext[m + 1]の位置から照合を続けます。

なぜ線形時間なのか

論文は照合段階のコストを次のように数えます。各ステップで、テキストのポインタが一つ進むか、パターンが右へ動きます。どちらもn回（テキストの長さ）を超えて動けないので、表を作ったあとの照合は多くても2nステップです。上のコードに当てはめると、while が1回回るたびにkが減り、kはテキスト1文字あたり最大1しか増えないので、while の繰り返しは合計でnを超えません。表を作るO(m)を足すと、全体はO(m + n)です。論文は、これらのO記法の定数がアルファベットの大きさに依存しないことも強調しています。2004年のPrincetonの講義資料のまとめの表も、KMPの最悪のコストを文字比較2N回、単純な探索の最悪をMN回としています。

テキストを後戻りしないことには、時間以外の意味もあります。論文は、テキストを外部ファイルから読む場合でも内部メモリはO(m)個分あればよいと書いています。読み終えたテキストを保持しておく必要がないからです。

nextを使う理由：1文字にとどまる時間

全体が線形だという結論は、fを使っても変わりません。論文の第5節も、第2節のアルゴリズムはnextの代わりにfを使っても正しく線形時間で動くと書いています。違いは、テキストの1文字を前にして表を何回たどって下がりうるかにあります。

論文は、nextを使えば、テキストの1文字を読む間にj := next[j]が連続して実行される回数は多くても1 + log_φ mであるという定理を証明しています。φ = (1 + √5)/2 ≈ 1.618は黄金比です。この上限はこれ以上下げられません。フィボナッチ文字列（この記事ではs₁ = b、s₂ = a、sₙ = sₙ₋₁sₙ₋₂と書きます）が最悪の場合を作り、論文の例では長さ21のパターンs₈のj = 20で不一致が起きると、jは20、12、7、4、2、1、0と順にたどりえます。

fを使うと、この定理は成り立ちません。論文の例はパターンaᵐです。f[j] = j − 1なので、テキストaᵐ⁻¹b…と照合してm文字目で食い違うと、j := f[j]がm回実行され、同じテキスト文字をパターンの文字とm − 1回むだに比較してから、ようやくテキストが次の文字へ進みます。同じパターンのnextを上の関係式で計算すると、すべてのjでnext[j] = 0になる（この記事による計算です）ので、一度でパターン全体を飛ばします。上のPythonコードはfに当たる表を使うので、この場合は1文字に長くとどまることがありますが、前の節の論証のとおり、全体の繰り返し回数はやはりnを超えません。入力をリアルタイムで受け取り、文字と文字の間の遅延が問題になるときに、nextが意味を持ちます。

オートマトンとしてのKMP：PrincetonのKMP.java

PrincetonのAlgorithms第4版のウェブサイトにある KMP.java は、同じ考え方を決定性有限オートマトン（DFA）として実装しています。状態jは「パターンの先頭j文字が一致している」という意味で、dfa[c][j] は状態jで文字cを読んだあとの状態です。コードを読むと、作り方は次のとおりです。

再開状態Xを0にします。状態0でパターンの先頭文字を読むと状態1へ進みます。
j = 1からm − 1まで、不一致の欄は状態Xの欄をそのまま写し、パターンのj文字目（0から数える）の欄だけをj + 1にします。
Xを「状態Xでその文字を読んだあとの状態」に更新します。Xは、パターンの2文字目から現在の文字までをオートマトンに入れたときに行き着く状態です。

探索は、テキストの1文字ごとに j = dfa[c][j] を1回実行するループ一つで、jがmになったら止まります。表をたどって下がる内側のループがないので、テキスト1文字あたりの仕事は常に表の参照1回です。その代わり、表はアルファベットの大きさに比例して大きくなります。このファイルのJavadocは、最悪の場合の時間がn + mRに比例し、追加の領域がmRに比例すると書いています（Rはアルファベットの大きさ）。文字列を受け取るコンストラクタはR = 256に固定しています。文字の値をそのまま配列の添字に使うコードなので、このコンストラクタでは値が256以上の文字が来ると表の範囲を外れます。何を1文字と数えるかはそれ自体が別の問題で、文字数がツールごとに違う理由で扱いました。

二つの挙動も確認しておきます。search() は最初の出現位置だけを返し、見つからないときは-1ではなくテキストの長さnを返します。同じサイトの5.3節のページは、KMPplus.java という改良版がアルファベットの大きさに関係なくM + Nに比例する時間と領域で動くと紹介しています。この記事ではそのファイルは開いていません。

論文の第7節の歴史も、この対比につながります。Morrisは1969年の夏にCDC 6400用のテキストエディタを作っていて、テキストファイルを後戻りしない方法を探し、有限オートマトンの理論をモデルにしてこのアルゴリズムに相当する方法を考案しました。Knuthはそれとは別に、Cookの定理をChesterのオートマトンに適用する過程をたどって同じ仕組みを取り出し、PrattがKnuthのデータ構造を修正して実行時間がアルファベットの大きさに依存しないようにしました。2004年のPrincetonの講義資料は二値アルファベットを例に、一致すれば必ず次の状態へ進むので、不一致のときに行く状態だけを保存すればよいと説明しています。アルファベットが大きいときは、同じテキスト文字についてnextを何回かたどることで、遷移表の1マスの代わりにします。

実際に速いのか

論文はここに但し書きを付けています。第3節は、第2節の単純な形は現実的なデータでは単純な探索に太刀打ちできないだろうと書いています。単純な探索の最悪はm × nですが、そのような場合が実際に起きる可能性は低いからです。アルファベットが大きいと部分一致そのものがまれで、パターンの先頭文字で食い違うというよくある場合を処理するのに、単純な形は不要な手順を多く踏みます。論文は先頭文字を特別扱いし、終端の検査を減らした改良版を示し、この形はたいてい単純な探索より速く動くだろうと書いています。この記事では性能を自分で測定していません。平均と最悪の差が大きいアルゴリズムの別の例と、標準ライブラリがその最悪をどう防いでいるかは、クイックソートはいつO(n²)になるのかで扱いました。

同じ論文の第8節は1976年に追加された後記で、BoyerとMoore（そして独立にGosper）による、パターンの最後の文字から比較してテキストを読み飛ばす方法を扱っています。アルファベットが大きければ、平均してテキストの文字を約n/m個調べるだけで済むと説明しています。複数のパターンを同時に探す問題は、nextの計算を一般化したトライによる方法につながり、論文はAhoとCorasickがこれを独立に発見したと書いています。

まとめるときに確認すること

添字の規則：論文のfとnextは1から数え、「次に比較するパターンの位置」を持ちます。0から数える実装はふつう「重なりの長さ」を持つので、1ずれます。上のコードの border[i] はi ≤ m − 2でf[i + 2] − 1で、最後の項目border[m − 1]には論文のf表に対応する欄がありません。
fとnext：どちらも全体ではO(m + n)です。テキストの1文字にとどまる回数を1 + log_φ m以下に抑えるのはnextです。
すべての出現：出現を見つけたあと、kを0ではなく表の値まで下げないと、重なった出現を見落とします。
DFAによる実装：テキスト1文字あたりの仕事は一定ですが、表はm × Rの大きさです。algs4の KMP.java はR = 256を既定にし、最初の出現だけを探し、見つからなければnを返します。
性能：O(m + n)は最悪の場合についての保証です。典型的な入力で単純な探索より速いかどうかは実装とデータ次第で、論文自身が単純な形ではそうならないかもしれないと書いています。

参考にした資料

Donald E. Knuth, James H. Morris, Jr., Vaughan R. Pratt, Fast Pattern Matching in Strings, SIAM Journal on Computing 6(2), 323–350ページ, 1977年6月（Johns Hopkins大学のサイトに置かれた写し）
Robert Sedgewick, Kevin Wayne, KMP.java, Algorithms第4版のコード（ファイルの著作権表示は2002–2025）
Robert Sedgewick, Kevin Wayne, 5.3 Substring Search, Algorithms第4版ウェブサイト（ページの最終更新表示は2017年12月21日）
Kevin Wayne, String Searching, Princeton COS 226講義資料, 2004年春

すべての資料は2026年10月16日に確認しました。