データ構造とプログラミング技法 （第10回） ー文字列照合（KMP法、BM法）ー
文字列照合 text中のpatの位置（複数可）を求める。
単純照合法 ｊはtext中の照合位置 iはpat中の照合位置 nはtextの長さ、 mはpatの長さ
単純照合法の無駄
単純照合法の無駄： 常に大きくスキップできる訳ではない
KMP法 text中のk番目の文字で、patのi番目の文字との比較に失敗した時、 textのk`番目と、patのnext[i]番目の文字との比較から再開する。 next[i]
next[i]の例 ABABBA 0 1 0 1 3 0 ０：共通文字列は存在しない→空であると想定しても，その直後の文字が同じなので矛盾する １：共通文字列は存在しない→空であると想定すると，その直後の文字と先頭文字が異なるため矛盾しない ３：共通文字列はAB→直後の文字もAとBで不一致
next[i]の例（続き） ABCDABD 0 1 1 1 0 1 3 ０：共通文字列は存在しない→空であると想定しても，その直後の文字が同じなので矛盾する １：共通文字列は存在しない→空であると想定すると，その直後の文字と先頭文字が異なるため矛盾しない ３：共通文字列はAB→直後の文字もAとBで不一致
KMP法:アルゴリズム
BM法:アイデア１ パターンの末尾から照合し,照合に失敗したテキストの 側の文字種が、パターン中の照合に失敗した位置より も左にあるかどうかを探す。
BM法:アイデア１の実現法
BM法:アイデア２ k+m-i
BM法:shift(j)
BM法:アルゴリズム