KMP算法的前缀表

Question

我正在研究KMP算法。尽管这个算法很容易理解，但我在这里有一个疑问。

前缀表算法：

void prefixTable(char p[], int m){
     int i=1, j=0, F[0] = 0;
     while(i<m){
        if(p[i]==p[j]){
            F[i]=j+1;
            i++;
            j++;
        }else if(j>0){
            j=F[j-1];
        }else{
            F[i]=0;
            i++;
        }
     }
}

​

​

如上面的图像步骤5所示，i=5，j=3，j=Fj-1作为j>0执行.

为什么我们要用Fj-1？为什么我们不能直接使用F呢？如何保证算法的正确性？

Answer 1

J是模式中的位置。

如果模式被处理到某个位置> 0，那么如果模式包含其本身的前缀，则不能将模式移动到第一个(0)位置。

应用于您的示例:模式是ababaca。尝试在文本abababaca中找到它

• 该算法将处理文本，直到模式为ababa|baca的ababa|c为止。
• 将j设置为F= 0，意味着将模式设置为|ababac，这永远不会与baca匹配(请注意，我不会被更改)
• 将j设置为F4 = 3，意味着将模式设置为aba|bac，这将与baca匹配
• 匹配之后，模式处于状态ababac|中，文本位于状态abababac|a中，很明显，找到的模式是ab[ababac]a。