一尘不染

了解Knuth-Morris-Pratt算法

algorithm

谁可以给我解释一下这个?我一直在阅读它,但仍然很难遵循。

文字:ababdbaababa
模式:ababa

ababa的表是-1 0 0 1 2。

我想我了解表的构造方式,但是一旦发生不匹配,我就不知道如何进行移位。似乎我们在移位时甚至不使用表格?

我们什么时候使用桌子?


阅读 246

收藏
2020-07-28

共1个答案

一尘不染

发生不匹配时使用该表。让我们将模式应用于您的文本:

您开始将文本与模式匹配,并从第一个位置开始测试模式是否可以在文本中显示。你比较text[1]pattern[1]和原来是一场比赛。你做同样的text[2]text[3]text[4]

当您想text[5]与之匹配时,pattern[5]没有匹配项(d<>
a)。然后,您知道您的模式将不会从第一个位置开始。然后,您可以重新开始位置2的匹配,但是效率不高。您 现在 可以 使用该表

错误发生在,pattern[5]所以您转到table[5]2。这表明您可以使用2个 已经匹配的字符 再次开始在当前位置进行 匹配
。不必开始匹配位置2,您可以从先前的位置(1)+ table[5](2)=
3开始。的确,如果我们看一下text[3]text[4],我们将看到它pattern[1]和和相等pattern[2]

表格中的数字告诉您发生错误时已经匹配了多少个位置。在这种情况下,下一个模式的2个字符已经匹配。然后,您可以立即开始匹配位置3,并跳过位置2(因为从位置[2]开始找不到该模式)。

2020-07-28