アルゴリズム図鑑 増補改訂版 絵で見てわかる33のアルゴリズム

 このように、クヌース

–

モーリス

–

プラット法は「パターンを一気にずらすことができ

る」、「照合位置を後戻りさせず前に進めることができる」という

2

つのアイデアを用いて、単

純なアルゴリズムを高速化させています。パターンからずらすべき文字数を計算する前処理

は

O

（

m

）、 実 際 の文字列照合は

O

（

n

）時 間 でできますので、全 体 で

O

（

n

＋

m

）時 間 になります。



… a b c a b ………





a b c a b b a

アルゴリズムとターンの

1

文字照合ていのの

2

文字「

a b

」は

て合は

5

文字分は

3

文字分



… a b c a b ………





a b c a b b a

てターンの

1



2

文字は合ていのて

3

文字照合開

いはテキストのと

1

にに

21

22

つり文字照合

はテキストはり

先と

りめいの