wiki:GB11921/2013-05-20

データ構造とアルゴリズム 第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 8 years ago Last modified on 05/20/2013 03:01:46 PM