Download presentation
Presentation is loading. Please wait.
1
データ構造とプログラミング技法 （第10回） ー文字列照合（KMP法、BM法）ー
2
文字列照合 text中のpatの位置（複数可）を求める。
3
単純照合法 ｊはtext中の照合位置 iはpat中の照合位置 nはtextの長さ、 mはpatの長さ
4
単純照合法の無駄
5
単純照合法の無駄： 常に大きくスキップできる訳ではない
6
KMP法 text中のk番目の文字で、patのi番目の文字との比較に失敗した時、
textのk`番目と、patのnext[i]番目の文字との比較から再開する。 next[i]
7
next[i]の例 ABABBA ０：共通文字列は存在しない→空であると想定しても，その直後の文字が同じなので矛盾する １：共通文字列は存在しない→空であると想定すると，その直後の文字と先頭文字が異なるため矛盾しない ３：共通文字列はAB→直後の文字もAとBで不一致
![next[i]の例 ABABBA ０：共通文字列は存在しない→空であると想定しても，その直後の文字が同じなので矛盾する. １：共通文字列は存在しない→空であると想定すると，その直後の文字と先頭文字が異なるため矛盾しない.](http://slidesplayer.net/slide/14286677/89/images/7/next%5Bi%5D%E3%81%AE%E4%BE%8B+ABABBA+%EF%BC%90%EF%BC%9A%E5%85%B1%E9%80%9A%E6%96%87%E5%AD%97%E5%88%97%E3%81%AF%E5%AD%98%E5%9C%A8%E3%81%97%E3%81%AA%E3%81%84%E2%86%92%E7%A9%BA%E3%81%A7%E3%81%82%E3%82%8B%E3%81%A8%E6%83%B3%E5%AE%9A%E3%81%97%E3%81%A6%E3%82%82%EF%BC%8C%E3%81%9D%E3%81%AE%E7%9B%B4%E5%BE%8C%E3%81%AE%E6%96%87%E5%AD%97%E3%81%8C%E5%90%8C%E3%81%98%E3%81%AA%E3%81%AE%E3%81%A7%E7%9F%9B%E7%9B%BE%E3%81%99%E3%82%8B.+%EF%BC%91%EF%BC%9A%E5%85%B1%E9%80%9A%E6%96%87%E5%AD%97%E5%88%97%E3%81%AF%E5%AD%98%E5%9C%A8%E3%81%97%E3%81%AA%E3%81%84%E2%86%92%E7%A9%BA%E3%81%A7%E3%81%82%E3%82%8B%E3%81%A8%E6%83%B3%E5%AE%9A%E3%81%99%E3%82%8B%E3%81%A8%EF%BC%8C%E3%81%9D%E3%81%AE%E7%9B%B4%E5%BE%8C%E3%81%AE%E6%96%87%E5%AD%97%E3%81%A8%E5%85%88%E9%A0%AD%E6%96%87%E5%AD%97%E3%81%8C%E7%95%B0%E3%81%AA%E3%82%8B%E3%81%9F%E3%82%81%E7%9F%9B%E7%9B%BE%E3%81%97%E3%81%AA%E3%81%84..jpg "３：共通文字列はAB→直後の文字もAとBで不一致.")
8
next[i]の例（続き） ABCDABD 0 1 1 1 0 1 3
０：共通文字列は存在しない→空であると想定しても，その直後の文字が同じなので矛盾する １：共通文字列は存在しない→空であると想定すると，その直後の文字と先頭文字が異なるため矛盾しない ３：共通文字列はAB→直後の文字もAとBで不一致
![next[i]の例（続き） ABCDABD](http://slidesplayer.net/slide/14286677/89/images/8/next%5Bi%5D%E3%81%AE%E4%BE%8B%EF%BC%88%E7%B6%9A%E3%81%8D%EF%BC%89+ABCDABD.jpg "０：共通文字列は存在しない→空であると想定しても，その直後の文字が同じなので矛盾する. １：共通文字列は存在しない→空であると想定すると，その直後の文字と先頭文字が異なるため矛盾しない. ３：共通文字列はAB→直後の文字もAとBで不一致.")
9
KMP法:アルゴリズム
10
BM法:アイデア１ パターンの末尾から照合し,照合に失敗したテキストの 側の文字種が、パターン中の照合に失敗した位置より
も左にあるかどうかを探す。
11
BM法:アイデア１の実現法
12
BM法:アイデア２ k+m-i
13
BM法:shift(j)
14
BM法:アルゴリズム
Similar presentations
