string - Knuth-Morris-Pratt アルゴリズムを理解する

Question

誰かが私にこれを説明できますか？私はそれについて読んでいますが、まだ理解するのは難しいです.

テキスト: ababdbaababa
パターン: ababa

ababa のテーブルは -1 0 0 1 2 です。

テーブルがどのように構築されているかは理解していると思いますが、ミスマッチが発生した場合にシフトする方法がわかりません。シフト時にテーブルすら使わないみたい？

テーブルはいつ使用しますか？

Answer 1

このテーブルは、不一致が発生したときに使用されます。パターンをテキストに適用しましょう。

テキストとパターンのマッチングを開始し、最初の位置から始めて、パターンがテキスト内にあるかどうかをテストします。と比較text[1]するpattern[1]と、一致することがわかります。text[2]、text[3]およびについても同じことを行いtext[4]ます。

text[5]一致したいときは一致しpattern[5]ません（d<> a）。これで、パターンが最初の位置から始まらないことがわかります。その後、2 位のマッチングを最初からやり直すこともできますが、それは効率的ではありません。これでテーブルを使用できます。

The error occured at pattern[5]so you go to which is 2. これは、すでに一致table[5]した 2 文字で現在の位置から再び一致を開始できることを示しています。一致する位置 2 を開始する代わりに、以前の位置 (1) + (2)=3 から開始できます。実際、 と を見ると、それぞれとに等しいことがわかります。table[5]text[3]text[4]pattern[1]pattern[2]

表の数字は、エラーが発生したときにすでに一致している位置の数を示しています。この場合、次のパターンの 2 文字が既に一致しています。次に、すぐに位置 3 のマッチングを開始し、位置 2 をスキップできます (位置 [2] から始まるパターンが見つからないため)。