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

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

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

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

2. KMP法

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

3. BM法

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


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