2013年6月17日月曜日

[練習] 文字列探索アルゴリズム

昨日やった文字列内のパターン検索。grepを自分で実装する時とかに使う。


1. シンプルなアルゴリズム

1文字づつずらして見ていく方法。最も単純。


2. KMP法

1文字ずつずらすのではなくて、次に比較させる場所を記憶しておく。
アルゴリズムが複雑な分、実は1のシンプルなアルゴリズムの方が早い時もある。


3. BM法

現実的な早い方法。パターンを後ろから前に対象文字列と照合していく。


最近なかなか時間が取れないのが悩みどころ。

0 件のコメント:

コメントを投稿