データ構造とアルゴリズム 第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を右シフトさせることにより、単純法よりもはるかに高速な文字列検索処理が可能
Last modified 11 years ago
Last modified on 05/20/2013 03:01:46 PM