KMP手算失效函数/next数据方法(个人感觉最快方法）

2301_77207297

501人浏览 · 2025-07-21 17:22:09

2301_77207297 · 2025-07-21 17:22:09 发布

话不多说，直接举例子展示：

1 模式串T：abaabc,求其失效函数

①首字符的f[ ]=-1，第二个字符的f[ ]=0（铁律）

第一步结果
下标	0	1	2	3	4	5
字符	a	b	a	a	b	c
f[ ]/next	-1	0

②求T[2]的失效函数值，看其前一个字符b,f[1]=0，下标为0的字符是a，a和b不相等，无法往前走了，则用f[0]（失效函数值）+1，即0作为T[2]的失效函数值。

第二步结果
下标	0	1	2	3	4	5
字符	a	b	a	a	b	c
f[ ]/next	-1	0	0

③求T[3]的的失效函数值，看其前一个字符a,f[2]=0，下标为0的字符是a，a和a相等，用0(下标值）+1，即1作为T[3]的失效函数值。

第三步结果
下标	0	1	2	3	4	5
字符	a	b	a	a	b	c
f[ ]/next	-1	0	0	1

④求T[4]的失效函数值，看其前一个字符a,f[3]=1，下标为1的字符是b，b和a不相等，继续往前走，f[1]=0,下标为0的字符是a,a和a相等，用0(下标值）+1，即1作为T[4]的失效函数值。

第四步结果
下标	0	1	2	3	4	5
字符	a	b	a	a	b	c
f[ ]/next	-1	0	0	1	1

⑤求T[5]的失效函数值，看其前一个字符b,f[4]=1,下标为1的字符是b,b和b相等，用1（下标值）+1，即2作为T[5]的失效函数值。

下标	0	1	2	3	4	5
字符	a	b	a	a	b	c
f[ ]/next	-1	0	0	1	1	2

方法总结

①计算字符A的失效函数值，看其前面一个字符B，将B和下标为 B的失效函数值的字符C作比较；

②如果B和C相等，则将C的下标+1作为A的失效函数值；

③若B和C不相等，继续向前，将B和下标为 C的失效函数值的字符D作比较；

④若相等，则将D的下标+1作为A的失效函数值；（同②）

⑤若不相等继续向前，其实是在重复②-④步

⑥直至找到首字符Z仍然不相等，则将 Z的下标+1作为A的失效函数值（也就是-1+1=0）。

2 模式串：abcaabbabcabaacbacba,求其失效函数（附上答案，可以自查）

┏━━━━━━━━━┓
┃ 答案 ┃
┗━━━━━━━━━┛
┏━━━━━━━━━┓
┃ 在下方
┗━━━━━━━━━┛

下标	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19
字符	a	b	c	a	a	b	b	a	b	c	a	b	a	a	c	b	a	c	b	a
f[]	-1	0	0	0	1	1	2	0	1	2	3	4	2	1	1	0	0	1	0	0

存档-KMP算法代码实现

haystack-匹配串，needle-模式串

class Solution {
public:
    int strStr(string haystack, string needle) {
        //KMP算法
        //先构造匹配串的next数组
        if(needle.size()==0) return 0;
        vector<int> next(needle.size());
        next[0]=0;
        for(int i=1,j=0;i<needle.size();i++){
            while(j>0 &&needle[i]!=needle[j]){
                j=next[j-1];
            }
            if(needle[i]==needle[j]){
                j++;
            }
            next[i]=j;
        }

        //匹配过程
        for(int i=0,j=0;i<haystack.size();i++){
            while(j>0 && haystack[i]!=needle[j]){
                j=next[j-1];
            }
            if(haystack[i]==needle[j]){
                j++;
            }
            if(j==needle.size()){
                return i-needle.size()+1;
            }
        }
        return -1;
    }
};