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

Question

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

abababca
0 0 1 2 3 4 0 1

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

在得到上述文本的索引4之后,我们length(l)=5;通过查看table[l-1]=3;根据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我们发现模式),在给定的例子中我们发现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的情况也是如此.但是'a'与'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

Answer 2

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

在 KMP 算法中，实际上，您计算的值与表中几乎相同（这通常称为前缀函数）。因此，当您到达文本中的位置 i 时，您需要计算文本中以位置 i 结尾的子字符串的最大长度，该子字符串等于模式的某个前缀。很明显，当且仅当该子字符串的长度等于模式的长度时，您就在文本中找到了该模式。那么，如何快速统计这个前缀函数值呢？（我想您使用某种 O(n^2) 算法对模式进行计数，但速度不够快）。假设我们已经对i-1文本的第一个符号完成了所有操作，现在正在处理位置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。