本文主要是介绍KMP 失配函数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
//求子模板串的模式值f[n]的函数
//f[i]表示以i为下标的字符前边有几个跟开头重复的字符
void getFail(char *p, int *f)
{
int m=strlen(p);
f[0]=f[1]=0;
for(int i=1; i<m; ++i)
{
int j=f[i];
while(j && p[i]!=p[j])j=f[j];
f[i+1] = p[i]==p[j]?1+j:0;
}
}
T t0 t1 … ts-1 ts ts+1 ts+2 … ts+j-1 ts+j ts+j+1 … tn-1
‖ ‖ ‖ ‖ ‖
P p0 p1 p2 … pj-1 pj pj+1
则有 ts ts+1 ts+2 … ts+j = p0 p1 p2 …pj (1)
为使模式 P 与目标 T 匹配，必须满足
p0 p1 p2 …pj-1 …pm-1 = ts+1 ts+2 ts+3 … ts+j … ts+m
如果 p0 p1 …pj-1 p1 p2 …pj (2)
则立刻可以断定
p0 p1 …pj-1 ts+1 ts+2 … ts+j
下一趟必不匹配
同样，若 p0 p1 …pj-2 p2 p3 …pj
则再下一趟也不匹配，因为有
p0 p1 …pj-2 ts+2 ts+3 … ts+j
直到对于某一个“k”值，使得
p0 p1 …pk+1 pj-k-1 pj-k …pj
且 p0 p1 …pk = pj-k pj-k+1 …pj
则 p0 p1 …pk = ts+j-k ts+j-k+1 … ts+j
‖ ‖ ‖
pj-k pj-k+1 … pj
k 的确定方法
当比较到模式第 j 个字符失配时， k 的值与模式的前 j 个字符有关，与目标无关。
利用失效函数 f (j)可描述。
利用失效函数 f (j) 的匹配处理
如果 j = 0，则目标指针加 1，模式指针回到 p0。
如果 j > 0，则目标指针不变，模式指针回到 pf(j-1)+1。
若设 模式 P = p0 p1…pm-2 pm-1
这篇关于KMP 失配函数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
