问理解Knuth-Morris-Pratt算法

EN

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

您开始将文本与模式进行匹配，并从第一个位置开始测试您的模式是否可以是文本。你将text[1]与pattern[1]进行比较，结果是匹配的。您可以对text[2]、text[3]和text[4]执行相同的操作。

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

错误发生在pattern[5]，所以你转到table[5]，它是2。这告诉你，你可以用2个已经匹配的字符在当前位置再次开始匹配。你可以从你之前的位置(1) + table[5] ( 2 )=3开始，而不是从位置2开始。实际上，如果我们看看text[3]和text[4]，我们会看到它分别等于pattern[1]和pattern[2]。

表中的数字告诉您发生错误时已匹配的位置数。在这种情况下，下一个模式的2个字符已经匹配。然后，您可以立即开始匹配位置3并跳过位置2(因为从position2开始无法找到模式)。

在这里，我已经简要地描述了计算前缀函数和在这里切换文本。

​

​

欲了解更多信息，请登录：Knuth–Morris–Pratt string search algorithm 。

在文本中切换：

Text:     ABC ABCDAB ABCDABCDABDE
Pattern : ABCDABD

方案1 -在模式和文本中有/有一些匹配的字符。

例1:这里有3匹配字符。

​

从表中获取3字符的值。(索引2，ABC)，即0，因此移位=3-0，即3

​

​

例2:这里有6匹配字符。

​

​

从表中获取6字符的值。(索引5，ABCDAB)即2，因此移位=6-2即4

​

​

Scenario 2 -如果没有匹配的字符，则移位1。

这是一个古老的话题，但希望将来搜索这个话题的人能看到它。上面给出的答案是好的，但我自己通过一个例子来了解到底发生了什么。

本文的第一部分取自wiki，我真正想详细说明的部分是这个回溯数组是如何构造的。

如下所示：

我们通过(相对人工的)算法运行，其中

W = "ABCDABD" and 
S = "ABC ABCDAB ABCDABCDABDE". 

在任何给定时间，算法都处于由两个整数确定的状态：

m，表示S内的位置，即W的预期匹配的开始

i W中的索引，表示当前考虑的字符。

在每个步骤中，我们将S[m+i]与W[i]和advance进行比较，如果它们相等的话。在运行开始时，这是这样描述的

              1         2  
m: 01234567890123456789012
S: ABC ABCDAB ABCDABCDABDE
W: ABCDABD
i: 0123456

我们将W的连续字符与S的“并行”字符进行比较，如果它们匹配，则从一个字符移动到下一个字符。然而，在第四步中，我们得到S3是一个空格，W3 = 'D'，不匹配。我们注意到在S的位置0和3之间没有出现'A‘，而不是在S1处再次搜索；因此，之前检查过所有这些字符，我们知道如果我们再次检查它们，就不可能找到匹配的开始。因此，我们继续下一个字符，设置m=4和i= 0。

              1         2  
m: 01234567890123456789012
S: ABC ABCDAB ABCDABCDABDE
W:     ABCDABD
i:     0123456

当我们在W6时，我们又有了一个差异，我们很快就得到了一个几乎完全匹配的"ABCDAB“。然而，就在当前部分比赛结束之前，我们传递了一个"AB“，这可能是新比赛的开始，所以我们必须考虑到这一点。因为我们已经知道这些字符与当前位置之前的两个字符匹配，所以我们不需要再次检查它们；我们只需重置m= 8，i=2并继续匹配当前字符。因此，我们不仅省略了以前匹配的字符S，而且还省略了之前匹配的字符W。

              1         2  
m: 01234567890123456789012
S: ABC ABCDAB ABCDABCDABDE
W:         ABCDABD
i:         0123456

然而，这个搜索立即失败，因为模式仍然不包含空格，所以在第一次尝试中，我们返回到W的开头，并从S的下一个字符开始搜索:m= 11，reset i= 0。

              1         2  
m: 01234567890123456789012
S: ABC ABCDAB ABCDABCDABDE
W:            ABCDABD
i:            0123456

我们再次偶然发现匹配"ABCDAB“，但下一个字符'C‘与单词W的最后一个字符'D’不匹配。如前所述，我们设置m= 15，从通向当前位置的两个字符的字符串"AB”开始，设置i= 2，并从当前位置继续匹配。

              1         2  
m: 01234567890123456789012
S: ABC ABCDAB ABCDABCDABDE
W:                ABCDABD
i:                0123456

这一次我们能够完成匹配，其第一个字符是S15。

上面的例子包含了算法的所有元素。目前，我们假设存在一个“部分匹配”表T，如下所述，它指示在当前匹配以不匹配结束的情况下，我们需要在何处查找新匹配的开始。T的条目被构造为，如果我们在比较Sm +i和Wi时从Sm开始的匹配失败，那么下一个可能的匹配将从S中的索引m+i- Ti开始(也就是说，Ti是我们在不匹配之后需要进行的“回溯”的量)。这有两个含义:第一，T= -1，这表明如果W不匹配，我们不能回溯，只需检查下一个字符；第二，尽管下一个可能的匹配将从索引m+i- Ti开始，如上例所示，但我们实际上不需要检查其后的任何Ti字符，因此我们将继续从W[Ti]进行搜索。

回溯数组构造：

所以我们称之为lps[]的回溯数组T[]，让我们看看我们是如何计算它的

lps[i] = the longest proper prefix of pat[0..i] 
            which is also a suffix of pat[0..i].

示例:对于模式“AABAACAABAA”，

lps[] is [0, 1, 0, 1, 2, 0, 1, 2, 3, 4, 5]

//所以我只想快速了解一下

 lps[0] is just 0 by default
 lps[1] is 1 because it's looking at AA and A is both a prefix and suffix
 lps[2] is 0 because it's looking at AAB and suffix is B but there is no prefix equal to B unless you count B itself which I guess is against the rules
 lps[3] is 1 because it's looking at AABA and first A matches last A
 lps[4] is 2 becuase it's looking at AABAA and first 2 A matches last 2 A
 lps[5] is 0 becuase it's looking at AABAAC and nothing matches C
 ...


 For the pattern “ABCDE”, lps[] is [0, 0, 0, 0, 0]
 For the pattern “AAAAA”, lps[] is [0, 1, 2, 3, 4]
 For the pattern “AAABAAA”, lps[] is [0, 1, 2, 0, 1, 2, 3]
 For the pattern “AAACAAAAAC”, lps[] is [0, 1, 2, 0, 1, 2, 3, 3, 3, 4]

这是完全有意义的，如果你认为it...if你不匹配，你想要尽可能地追溯，很明显，你回到多远(后缀部分)本质上是前缀，因为根据定义，你必须从第一个字符重新开始匹配。所以如果你的字符串看起来像

aaaaaaaaaaaaaaa..b..aaaaaaaaaaaaaaac和您在最后一个字符c上不匹配，然后您希望重用aaaaaaaaaaaaaaa作为新的头部，只要仔细考虑就可以了。