6

I have been trying to understand KMP algorithm. Still I didn't get the clear understanding of reasoning behind kmp algorithm. Suppose my text is bacbababaabcbab and pattern is abababca. By using the rule of length of longest proper prefix of sub(pattern) that matches the proper suffix of sub(pattern), I filled my table[].

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

Now I started applying KMP algorithm on the text with my pattern and table.

After coming to index 4 of above text, we have a match of length(l)=5; by looking at table[l-1]=3; As per KMP algorithm we can skip length up to 2 chars and can continue .

bacbababaabcbab
----xx|||
abababca

Here I am not getting the logic behind shifting. Why should we shift? Can somebody please clarify my confusion?

4

2 回答 2

5

要了解 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

在 brute-force 方法中，将图案一张一张地滑过文本并检查是否匹配。如果找到匹配项，则再次滑动 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 我们找到了模式），在给定的示例中，我们在 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' 不匹配</p> 

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

于 2014-07-15T08:47:58.040 回答
1

我不确定您是否仅在这一点上存在理解问题，因此，如果您不介意，我将描述（尽可能多地解释）整个算法。您的问题的答案可能在最后一段，但您最好通读一遍以更好地理解我的术语。

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

让我们比较一下 text[i] 和 pattern[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。

于 2013-09-14T18:54:48.003 回答