我正在研究 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=F[j-1]被执行为j>0。
为什么要取F[j-1]？为什么我们不能直接使用F[0]呢？ 它如何保证算法的正确性？
最佳答案
j 是模式中的位置。
如果模式被处理到某个位置 > 0，那么如果模式包含其自身的前缀，我们就不能将模式移动到第一个 (0) 位置。
应用于您的示例:模式是 ababaca。尝试在文本 abababaca 中找到它:
- 算法将处理文本直到
ababa|baca，其中模式为ababa|c - 将 j 设置为 F[0] = 0，意味着将模式设置为
|ababac，它永远不会匹配baca(注意 i 不会被更改)< - 将 j 设置为 F[4] = 3，意味着将模式设置为
aba|bac，这将匹配baca - 匹配后，模式处于状态
ababac|，文本处于状态ababac|a，很明显找到的模式是ab[ababac ]a
关于algorithm - KMP算法前缀表，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/38982121/