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

DA10