一致した分を捨てない — 文字列照合と失敗関数

ABABAC の失敗関数を計算すると次のとおりです(Python 3.14.6 / macOS 26.5.2 arm64、2026-10-07 実行)。

prefix function of ABABAC:
i   : [0, 1, 2, 3, 4, 5]
P[i]: ['A', 'B', 'A', 'B', 'A', 'C']
pi  : [0, 0, 1, 2, 3, 0]

位置4までの ABABA は、頭の ABA と尻の ABA が重なるので値が3です。最後の C は頭の A と合わないので0に戻ります。

次に、素朴法が苦手な本文 "A"*n+"B" とパターン "A"*10+"B" で、文字を比べた回数を数えました。KMP の列は走査中の比較で、表を作る比較(19回、n に依らない)は含みません。

n      naive_cmp   kmp_cmp(scan)  kmp_table_cmp  2n   kmp<=2n  found_at
100    1001        191            19             202   True   [90]
1000   10901       1991           19             2002  True   [990]
10000  109901      19991          19             20002 True   [9990]

素朴法は n が10倍になるたびに約10倍、1か所あたり11回です。 これはパターン長 m に比例する分で、全体は約 n×m 回です。KMP は 2n 未満に収まり、n に比例して増えるだけです。 見つけた位置は3つとも str.find の結果と一致することを確かめてあります。

ここで線を引いておきます。「2n 以下」は本教材の実測と下の説明であって、KMP の原論文の文言として引くものではありません(論文本文は取得できていません)。出版社の抄録が書いているのは次の範囲です。

An algorithm is presented which finds all occurrences of one given string within another, in running time proportional to the sum of the lengths of the strings.

別の構造で解くのが Rabin-Karp 法です。本文の長さ m の窓ごとにハッシュ値を作り、パターンのハッシュと比べます。窓を1文字ずらすときは、出ていく1文字と入ってくる1文字の分だけを直して次の窓のハッシュを得ます(ローリングハッシュ)。m 文字を読み直しません。

ハッシュが違えば確実に別の文字列で、同じなら文字を比べて確かめます。違う文字列が同じハッシュになる(衝突)と、確かめが無駄になります。論文の題 "Efficient randomized pattern-matching algorithms" が示すとおり、乱数を使う側の手法です。ハッシュの選び方に乱数を混ぜれば、入力を作る側は衝突を前もって狙えません。速さは最悪ではなく期待値で語られる——第3回で見た期待値と同じ型です。

実際の標準ライブラリはどうか。CPython 3.14 の Objects/stringlib/fastsearch.h の冒頭です(2026-10-07 取得)。

fast search/count implementation, based on a mix between boyer-moore and horspool, with a few more bells and whistles on the top.

If the strings are long enough, use Crochemore and Perrin's Two-Way algorithm, which has worst-case O(n) runtime and best-case O(n/k).

KMP そのものではありません。 ファイル内に KMP・Knuth・Morris の語はありません。Two-Way は、コメントの言う O(m) の準備(startup cost)を先に払って最悪を線形に抑える点で、KMP と同じ発想の別手法です。どちらを使うかは長さで切り替えます(n は本文長、m はパターン長)。

if (n < 2500 || (m < 100 && n < 30000) || m < 6) {
    return STRINGLIB(default_find)(s, n, p, m, maxcount, mode);
}
else if ((m >> 2) * 3 < (n >> 2)) {
    /* 33% threshold, but don't overflow. */

短いうちは default_find(boyer-moore と horspool の混合)、条件を超えると _two_way_find、どちらでもなければ途中で Two-Way へ移る adaptive_find です。この分岐は mode != FAST_RSEARCH(逆方向の検索でない)ときだけで、rfind は Two-Way を使いません。導入は 3.10 で、What's New はこう書いています。

Substring search functions such as str1 in str2 and str2.find(str1) now sometimes use Crochemore & Perrin’s “Two-Way” string searching algorithm to avoid quadratic behavior on long strings. (Contributed by Dennis Sweeney in bpo-41972)