labs.wakayama.ninja
文字列照合
一致情報や不一致文字を使って、無駄な比較を飛ばす様子を眺めます。
文字列照合とは
テキストの中から、探したいパターンがどこに現れるかを調べます。単純に1文字ずつずらす方法に対して、KMP法やBM法は失敗した比較の情報を使って大きくずらします。
テキスト BABABBBABAABA
パターン BABAAB
比較
失敗関数
眺め方
力任せ法 は、不一致になるたびにパターンを1文字だけ右へずらします。
KMP は、パターンの先頭と末尾がどれだけ重なっているかを使って戻り先を決めます。
BM は、右から比較し、不一致になったテキスト側の文字を使って大きくずらします。