string - 在 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 个字符的长度并继续。

bacbababaabcbab
----xx|||
abababca

这里我没有理解转移背后的逻辑。我们为什么要转移？有人可以澄清我的困惑吗？

Answer 1

要了解 KMP 算法背后的逻辑，您首先应该了解，此 KMP 算法为何优于蛮力算法。

Idea

模式转换后，朴素算法忘记了有关先前匹配符号的所有信息。所以它有可能一次又一次地重新比较一个文本符号和不同的模式符号。这导致其最坏情况复杂度为 Θ(nm)(n:文本长度，m:模式长度)。

Knuth、Morris 和 Pratt [KMP 77] 的算法利用了通过之前的符号比较获得的信息。它从不重新比较与模式符号匹配的文本符号。因此，Knuth-Morris-Pratt算法搜索阶段的复杂度为O(n)。

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

文本:bacbababaabcbab 图案:abababca

在暴力法中， 将图案一个一个地滑过文本并检查是否匹配。如果找到匹配项，则再次滑动 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= patternlength 我们找到了 pattern)，在给定的例子中我们发现不匹配在 j= 5 当 i=4 时，在文本中的索引 4+5=9 处发生不匹配。匹配的子字符串是 ababa ， **

• 为什么我们需要选择最长的正确前缀也是正确的后缀:

** 从上面:我们看到不匹配发生在模式以子字符串 ababa 结尾的 9 处。 现在，如果我们想利用迄今为止所做的比较，那么我们可以跳过(递增)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#SECTION0080 http://www.inf.fh-flensburg.de/lang/algorithmen/pattern/kmpen.htm