考え方例1

例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法）