KMP算法的前缀table

Question

我正在研究 KMP 算法。这个算法虽然说的通俗易懂，但我这里有一点疑惑

前缀table算法：

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=F[j-1]当j>0时执行。

为什么要取F[j-1]？为什么我们不能直接使用F[0]呢？它如何确保算法的正确性？

Answer 1

j 是模式中的位置。

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

应用于您的示例：模式是 ababaca。尝试在文本 abababaca:

中找到它

算法将处理文本，直到 ababa|baca 模式为 ababa|c
设置j为F[0] = 0，表示设置pattern为|ababac永远不会匹配baca（注意i不会改变）
设置 j 为 F[4] = 3，意味着将模式设置为 aba|bac，这将匹配 baca
匹配后，模式处于 ababac| 状态，文本处于 abababac|a 状态，很明显找到的模式是 ab[ababac]a

KMP算法的前缀table

Prefix table for KMP algorithm

algorithm

string-matching