在 KMP 算法中发生文本不匹配的转换背后的推理

Question

我一直在努力理解KMP算法。我仍然没有清楚地了解 kmp 算法背后的推理。假设我的文本是bacbababaabcbab的，模式是abababca的。通过使用与sub(pattern)的适当后缀相匹配的最长正确前缀sub(pattern)的长度规则，我填满了我的table[]。

a b a b

a b c a
0 0 1 2 3 4 0 1

现在我开始用我的模式和表格在文本上应用 KMP 算法。

来到上面文本的索引 4 后，我们通过查看table[l-1]=3;来获得length(l)=5;匹配 根据 KMP 算法，我们最多可以跳过 2 个字符的长度并可以继续。

巴巴巴
----xx|||
阿巴巴布卡

在这里，我没有得到转变背后的逻辑。我们为什么要转变？有人可以澄清我的困惑吗？

Answer 1

要理解KMP算法背后的逻辑，首先应该明白，这个KMP算法是如何比暴力算法更好的。

Idea

在模式发生变化后，朴素算法已经忘记了有关先前匹配的交易品种的所有信息。因此，它可能会一次又一次地将文本符号与不同的图案符号重新比较。这导致其最坏情况的复杂性为Θ（nm）（n：文本的长度，m：图案的长度）。

Knuth、Morris 和 Pratt [KMP 77] 的算法利用了通过先前的交易品种比较获得的信息。它从不重新比较与图案符号匹配的文本符号。因此，高德纳-莫里斯-普拉特算法搜索阶段的复杂性在 O（n） 中。

但是，为了分析其结构，必须对模式进行预处理。预处理阶段的复杂性为 O（m）。由于 m<=n，Knuth-Morris-Pratt 算法的整体复杂度为 O（n）。

文：巴巴巴巴图案：阿巴巴布卡

在蛮力方法中，在文本上逐个滑动图案并检查匹配项。如果找到匹配项，则再次滑动 1 以检查后续匹配项。

void search(char *pat, char *txt)
{
    int M = strlen(pat);
    int N = strlen(txt);
    /* A loop to slide pat[] one by one */
    for (int i = 0; i <= N - M; i++)
    {
        int j;
        /* For current index i, check for pattern match */
        for (j = 0; j < M; j++)
        {
            if (txt[i+j] != pat[j])
                break;
        }
        if (j == M)  // if pat[0...M-1] = txt[i, i+1, ...i+M-1]
        {
           printf("Pattern found at index %d n", i);
        }
    }
}

上述算法的复杂度为O（nm）。在上面的算法中，我们从未使用我们处理的比较数据，

Bacbababaabcbab   //let I be iterating variable over this text
Abababca    //j be iterating variable over pattern

当 i=0

和 j=0 时，存在不匹配（text[i+j]！=pat[j]），我们递增 i 直到匹配。当 i = 4 时，有一个匹配（text[i+j]==pat[j]），递增 j 直到我们发现不匹配（如果 j= 模式长度，我们找到了模式），在给定的例子中，我们发现 j=5 时 i=4 不匹配，文本中的 idex 4+5=9 处发生不匹配。匹配的子字符串是 ababa ，**

• Why we need to choose longest proper prefix which is also proper suffix :

**从上面：我们看到不匹配发生在 9 处，其中模式以子字符串 ababa 结尾。现在，如果我们想利用到目前为止所做的比较，那么我们可以跳过（增量）i 超过 1，然后比较的数量将减少，从而提高时间复杂度。
现在我们可以在处理的比较数据"ababa"上利用什么优势。如果我们仔细观察：字符串 ababa 的前缀 aba 与文本进行比较并匹配，后缀 aba 也是如此。但是"b"与"a"不匹配

Bacbababaabcbab
         ||||||            
         ||||| x
        |||| ||
        ababab

但根据幼稚的方法，我们将 i 增加到 5。但是通过查看我们知道，我们可以设置 i = 6，因为下一次出现 aba 发生在 6。因此，我们不是与文本中的每个元素进行比较，而是预处理模式以找到最长的正确前缀，该前缀也是正确的后缀（称为边框）。在上面的例子中，对于"ababa"，最长边框的长度是3（即aba）。所以递增：子字符串的长度 – 最长边框的长度 => 5-3 =2。
如果我们的比较在 aba 处失败，那么最长边界的长度是 1，j=3，所以递增 2 。

有关如何预处理的更多信息： http://www-igm.univ-mlv.fr/~lecroq/string/node8.html#SECTION0080http://www.inf.fh-flensburg.de/lang/algorithmen/pattern/kmpen.htm

Answer 2

我不确定你是否在这一点上理解有问题，所以，如果你不介意，我只会描述（尽可能多地解释）整个算法。你的问题的答案可能在最后一段，但你最好全部阅读，以便更好地理解我的术语。

在 KMP 算法期间，您实际上计算的值与表中的值几乎相同（这通常称为前缀函数）。因此，当您到达文本中的位置 i 时，您需要计算文本中以位置 i 结尾的子字符串的最大长度，该长度等于模式的某个前缀。很明显，当且仅当此子字符串的长度等于模式的长度时，您已经在文本中找到了模式。那么，如何快速计算此前缀函数值呢？（我想你使用一些 O（n^2） 算法为模式计算这些，这还不够快）。假设我们已经为文本的前 i-1 个符号做了所有操作，我们现在正在使用位置 i .我们还需要文本前一个符号的前缀函数值：p[i-1] .

让我们比较一下文本[i]和模式[p[i-1]]（如果你不介意的话，从0开始索引）。我们已经知道pattern[0:p[i-1]-1] == text[i-1+p[i-1],i-1]：这就是p[i-1]的定义。所以，如果text[i] == pattern[p[i-1]]，我们现在知道pattern[0:p[i-1]] == text[i-1+p[i-1]，i]'，这就是为什么p[i] = p[i - 1]。但有趣的部分始于text[i] != pattern[p[i-1]].

当这些符号不同时，我们开始跳跃。这样做的原因是我们希望尽快找到下一个可能的前缀。那么，我们如何做到这一点。只需查看此处的图片并按照说明进行操作（黄色部分是为text[i-1]找到的子字符串）。我们试图找到一些字符串s：s:=s1+text[i] 。由于前缀函数定义，s1=s2, c=test[i] .但是我们已经知道（通过查找text[i-1]的值）图片中的两个黄色部分是相同的，所以s3实际上等于s1，所以s3=s1。所以我们可以找到s1的长度：它是table[p[i-1]]。所以现在如果c1=text[i]，我们应该停下来：我们已经找到了p[i]，它是s1.length + 1。如果c1!=text[i]，我们可以重复相同的跳跃，现在查看模式的前 table[table[p[i-1]]] 个符号，因此我们继续直到找到答案，或者在这种情况下我们得到前 0 个符号p[i]:=0 .