== データ構造とアルゴリズム 第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を右シフトさせることにより、単純法よりもはるかに高速な文字列検索処理が可能