文字列マッチ

アルゴリズムの一分野である文字列マッチ。

ここでは【書籍】IntroductionToAlgorithmsの文字列マッチを読んでいったメモを中心に。32.3のあたり。

ノーテーション

PngNote1

有限オートマトン

ノーテーション

PngNote2

状態遷移

PngNote2

acceptとreject

状態遷移を続けていって今の状態qがAのメンバならMはここまでの入力をacceptしたといい、そうでないなら入力はrejectされたという。

Knuth-Morrits-Prattアルゴリズムとprefix関数

オートマトンは遷移関数の事前計算の計算量が多い。 そこでその改善にprefix関数を使ってオンデマンドに計算する、というのがKMPアルゴリズムのアイデア。

Prefix関数

PngNote3

Prefix関数を使ったマッチのアルゴリズム

次の文字が一致しなかった時にパイを遡って次の文字と一致するprefixを探して続ける、というもの。 これがオーダーnになるのはなかなかきわどい分析が必要でちょっと難しいが、 アルゴリズムが正しい事とまぁまぁ早そうな事は容易に理解出来る。