クヌース–モリス–プラット法

基本的な考え方

テキスト（探索対象文字列）と パターン（探索文字列）
・「テキスト」から「単語で指定されたパターン」を探すにあたり、「不一致となった位置」と「単語自身の情報から次に照合を試すべき位置」を決定することで検索を効率化する

前処理
・「パターンに含まれる各文字」について、「その文字で不一 致になった際パターンをどれだけずらせばよいか」を調べて表にしておく

探索を行う
・上記表をもとにパターンをずらしていく

計算量
・O(n)

---

理論的には？

力任せ法よりも高速なアルゴリズム
・テキストとパターンの照合において後戻りは発生しないため、力任せ法（Brute Force Search）よりも高速なアルゴリズムとなる

---

現実的には？

問題点
・テーブルを作成するための前処理が複雑
・アルゴリズムが複雑な分だけオーバーヘッドが大きくなってしまう

短い文字列の場合
・結果的に力任せ法の方が効率が良いケースもある

例1

6文字パターン「REDRED」を探索

---

1文字目が不一致

スタート

テキスト	？	？	？	？	？	？	？
パターン	R	E	D	R	E	D

1文字目が不一致の場合
・「テキスト」位置情報を1つ進める
・「パターン」を1つ右へずらす
・「パターン」先頭から比較

テキスト	？	？	？	？	？	？	？
パターン	-	R	E	D	R	E	D

---

2文字目が不一致

スタート
・この時点では「デキスト」と「パターン」の1文字目が一致している

テキスト	R	？	？	？	？	？	？
パターン	R	E	D	R	E	D

2文字目が不一致の場合
・「パターン」を1つ右へずらす
・「パターン」先頭から比較
※「テキスト」を指すポインタ位置は 変わらないことに注意

テキスト	R	？	？	？	？	？	？
パターン	-	R	E	D	R	E	D

---

3文字目が不一致

スタート
・この時点では「デキスト」と「パターン」の1〜2文字目が一致している

テキスト	R	E	？	？	？	？	？
パターン	R	E	D	R	E	D

3文字目が不一致の場合
・「パターン」を2つずらす(パターンを1文字ずらしても、1文字目が一致しないことは明らかなため)
・「パターン」先頭から比較

テキスト	R	E	？	？	？	？	？	？
パターン	-	-	R	E	D	R	E	D

---

4文字目が不一致

スタート
・この時点では「デキスト」と「パターン」の1〜3文字目が一致している

テキスト	R	E	D	？	？	？	？	？
パターン	R	E	D	R	E	D

4文字目が不一致の場合
・「パターン」を3つずらす(パターンを1文字ずらしても、1文字目が一致しないことは明らかなため)
・「パターン」先頭から比較

テキスト	R	E	D	？	？	？	？	？	？
パターン	-	-	-	R	E	D	R	E	D

---

5文字目が不一致

スタート
・この時点では「テキスト」と「パターン」の1〜4文字目が一致している
・テキストの1文字目と4文字目は同じ文字Rになっている

テキスト	R	E	D	R	？	？	？	？
パターン	R	E	D	R	E	D

パターンを4つずらすと？
・テキスト4文字目のRを 見逃してしまう

テキスト	R	E	D	R	？	？	？	？	？
パターン	-	-	-	-	R	E	D	R	E

5文字目が不一致の場合
・「パターン」を3つずらす(パターンを1文字ずらしても、1文字目が一致しないことは明らかなため)
・「パターン」2文字目から比較を続行

テキスト	R	E	D	R	？	？	？	？	？
パターン	-	-	-	R	E	D	R	E	D

---

6文字目が不一致

スタート
・この時点では「デキスト」と「パターン」の1〜5文字目が一致している

テキスト	R	E	D	R	E	？	？	？
パターン	R	E	D	R	E	D

6文字目が不一致の場合
・「パターン」を3つずらす(パターンを1文字ずらしても、1文字目が一致しないことは明らかなため)
・「パターン」3文字目から比較

テキスト	R	E	D	R	E	？	？	？	？
パターン	-	-	-	R	E	D	R	E	D

---

考え方

パターンの i 文字目で失敗した
・0 から i - 1 文字はテキストとパターンが一致している 

ポイント
・パターンの i 文字目で失敗した時に、何文字ずらして再開するか

例1の場合
・1文字目で失敗 ＝＞ ずらし数 next[0] = 1
・2文字目で失敗 ＝＞ ずらし数 next[1] = 1
・3文字目で失敗 ＝＞ ずらし数 next[2] = 2
・4文字目で失敗 ＝＞ ずらし数 next[3] = 3
・5文字目で失敗 ＝＞ ずらし数 next[4] = 3
・6文字目で失敗 ＝＞ ずらし数 next[5] = 3


計算量
・O(n)


・
文字列検索（直感的な文字列検索とKMP法）

アルゴリズムの状態
・二つの整数 m と i で表される

m
・テキスト S 内の文字の位置
・単語 W にマッチする可能性のある位置

i
・その時点で照合中の W 内の文字の位置

検索開始時点の状態
・W の先頭と S の先頭から照合していく
・この例では4文字目の照合で S[3] が-、W[3] = 'R' となるため、不一致となる
・W 内でそこまでに照合された範囲で 'R' が 0 番目にしかないことから、そこまで照合した S の範囲内に 'R' が出現しないことは明らか
・具体的には、S[1] から S[3] までは W[0] とマッチすることはない
・そのため、次の照合を単純に S[1] から開始するのではなく、m = 4 および i = 0 として次の照合を開始する

m	0	1	2	3	4	5	6	7	8	9	0
S	B	L	U	-	B	L	U	E	B	L	-
W	B	L	U	E	B	L	E
i	0	1	2	3	4	5	6

m = 4 および i = 0 として次の照合を開始
・ここで、"BLUEBL" までマッチすることがわかる
・W[6] (S[10]) で不一致となる。但し、前回の不一致とは異なり、"BL" が2回出現していることに注意が必要
・この範囲での2回目の "BL" は W の先頭ともマッチするので、ここでは m = 8 および i = 2 として照合を再開する

m	0	1	2	3	4	5	6	7	8	9	0
S	B	L	U	-	B	L	U	E	B	L	-
W	-	-	-	-	B	L	U	E	B	L	E
i	-	-	-	-	0	1	2	3	4	5	6

m = 8 および i = 2 として照合を再開

m	0	1	2	3	4	5	6	7	8	9	0
S	B	L	U	-	B	L	U	E	B	L	-
W	-	-	-	-	B	L	U	E	B	L	E
i	-	-	-	-	0	1	2	3	4	5	6

コーディングに役立つ！ アルゴリズムの基本（7）：文字列の中から効率良くキーワードを探し出せ
文字列検索のアルゴリズム①(KMP法)
http://yamweb.comp.ae.keio.ac.jp/japanese/2011-A%E8%AB%96/9before%EF%BC%88%E6%96%87%E5%AD%97%E5%88%97%E6%8E%A2%E7%B4%A2+%E3%83%90%E3%83%83%E3%82%AF%E3%83%88%E3%83%A9%E3%83%83%E3%82%AF).pdf
文字列探索のKMP法を考えた人すごいと思う。



文字列探索

単純法、KMP法、BM法の違い
文字列の検索


文字列アルゴリズムの学びかた


・終了後→文字列探索