プログラミングの宝箱 アルゴリズムとデータ構造 (C magazine)
- 作者: 紀平拓男,春日伸弥
- 出版社/メーカー: ソフトバンククリエイティブ
- 発売日: 2003/06/14
- メディア: 単行本
- 購入: 4人 クリック: 25回
- この商品を含むブログ (40件) を見る
KMP法で引っかかったが、なかなか面白かった。
KMP法もBM法もどちらも、検索文字列中のある文字で一致しなかった場合に、どれだけ飛ばして検索を再開するかというのがキモだ。
そのためのテーブルを作っておくのだが、KMP法でそのテーブルを作る部分で引っかかってしまった。
あちこちに検索文の文字列へのインデックスや、検索文字列へのインデックスを出力するようにして、どうにか理解できた。
以下の検索例で、先頭についている数字列が、そのテーブルの内容である。
KMP法
BM法
a p p l e a p p l e f i g h t
0 0 0 0 0 0 0 1 2 3 4 5 6 0 0 0 0 0
text: apple apple apple apple apple fight
pattern: a
text: apple apple apple apple apple fight
pattern: p
text: apple apple apple apple apple fight
pattern: p
text: apple apple apple apple apple fight
pattern: l
text: apple apple apple apple apple fight
pattern: e
text: apple apple apple apple apple fight
pattern:
text: apple apple apple apple apple fight
pattern: a
text: apple apple apple apple apple fight
pattern: a
text: apple apple apple apple apple fight
pattern: a
text: apple apple apple apple apple fight
pattern: p
text: apple apple apple apple apple fight
pattern: p
text: apple apple apple apple apple fight
pattern: l
text: apple apple apple apple apple fight
pattern: e
text: apple apple apple apple apple fight
pattern:
text: apple apple apple apple apple fight
pattern: a
text: apple apple apple apple apple fight
pattern: a
text: apple apple apple apple apple fight
pattern: a
text: apple apple apple apple apple fight
pattern: p
text: apple apple apple apple apple fight
pattern: p
text: apple apple apple apple apple fight
pattern: l
text: apple apple apple apple apple fight
pattern: e
text: apple apple apple apple apple fight
pattern:
text: apple apple apple apple apple fight
pattern: a
text: apple apple apple apple apple fight
pattern: a
text: apple apple apple apple apple fight
pattern: a
text: apple apple apple apple apple fight
pattern: p
text: apple apple apple apple apple fight
pattern: p
text: apple apple apple apple apple fight
pattern: l
text: apple apple apple apple apple fight
pattern: e
text: apple apple apple apple apple fight
pattern:
text: apple apple apple apple apple fight
pattern: a
text: apple apple apple apple apple fight
pattern: p
text: apple apple apple apple apple fight
pattern: p
text: apple apple apple apple apple fight
pattern: l
text: apple apple apple apple apple fight
pattern: e
text: apple apple apple apple apple fight
pattern:
text: apple apple apple apple apple fight
pattern: f
text: apple apple apple apple apple fight
pattern: i
text: apple apple apple apple apple fight
pattern: g
text: apple apple apple apple apple fight
pattern: h
text: apple apple apple apple apple fight
pattern: t
Found
17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17
17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17
5 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17
17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17
17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17
17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17
17 10 17 17 17 6 4 2 1 3 17 17 7 17 17 17
8 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17
17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17
17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17
17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17
17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17
17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17
17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17
17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17
17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17
text: apple apple apple apple apple fight
pattern: apple apple fight
text: apple apple apple apple apple fight
pattern: apple apple fight
text: apple apple apple apple apple fight
pattern: apple apple fight
text: apple apple apple apple apple fight
pattern: apple apple fight
Found
いや、楽しかった。
いよいよ、残り3章だ。
