データ構造とアルゴリズム 第5週
文字列照合
表記法の定義
文字列 text[1..n]
第i番目の文字 text[1]
text[i..j」
i==jのときはtext[i]
i>jのときはNULL
text[1..n]があって、そのなかにpattern[1..m]があったら
単純照合法
一致したら文字列とパターンの両方とも1文字右に進む
一致しなかったらpat[1]から1文字ずつ照合
KMP法
まくらパターンにしたがって見逃しを避けつつ、text上をなるべく大幅にpatternを右シフトさせることにより、単純法よりもはるかに高速な文字列検索処理が可能