四十三庵

蔀の雑記帳

Knuth-Morris-Pratt String Search

  • 単純な文字列検索は検索対象の文章の長さNと検索ワードの長さMのO(MN)になる
  • KMPアルゴリズムを使うとO(N)でいける
    • ただし検索ワードのスキップ量があらかじめ設定されている場合
  • 発想としては、検索対象の文字を一文字ずつ照合していくと、 実は明らかにスキップできる文字もループ一回分になるので、それをスキップしよう、という考え。
  • 具体的には、検索ワードが「abc」で、cまで照合して一致しない判定になったなら、 xabxxxxx という状況なわけだが、単純な文字列検索のループだとbから探索し直しになってしまう。 ^
  • それだと非効率なので、abcのスキップ量として「112」を与えて、cで不一致になったら2つスキップして、 cではなかった文字をaがどうか探索するようにするのがKMPアルゴリズム
  • 本だとスキップ量はプログラマーが与える前提だったが、実際はスキップ量も計算しなきゃ行けない気がする。 SAC見るとなんかやっている?