【字符串】KMP

更新于 分类于 ， 阅读次数： 本文字数： 954 阅读时长 ≈ 1 分钟

KMP是判断字符串匹配的算法。

目标：找到字符串中与模板串相同子串的匹配位置/次数

理解：状态机，状态转移图，失配后不从头匹配。或者理解为，找失配函数=找最长前后缀

f[i]f[i] 为失配函数，TT 为模板串，PP 为需要匹配的串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
void match(char *T,char *P,int *f)
{
    int l1=strlen(T),j=-1,l2=strlen(P);
    for(int i=0;i<l2;i++)//遍历匹配串
    {
        //j：模板串中T[j]及之前的都已经与P[i-1]及之前匹配完成
        while(~j&&T[j+1]!=P[i])//T[j]之前均匹配，如果T[j+1]与P[i]不匹配
            j=f[j];//根据失配函数找到上一个匹配位置
        //整个序列都没有匹配的/匹配到了跳出循环
        if(T[j+1]==P[i])//如果是上述第二种情况
            j++;//模板串的匹配位置向后一位，即匹配到了原本的第j+1位
        if(j==l1-1)//如果匹配到了最后一位
        {
            printf("%d\n",i-j+1);
            j=f[j];//最后一位已匹配的情况下，根据失配函数找到下一位开始的位置
        }
    }
}
//寻找失配函数的过程：模板串的自身匹配
void get_f(char *T,int *f)
{
    int len=strlen(T),j=-1;
    f[0]=f[1]=-1;//初始化
    for(int i=1;i<len;i++)//从第二位开始匹配
    {
        //j：模板串T[j]及之前的都已经与T[i-1]匹配完成
        //以下同上
        while(~j&&T[j+1]!=T[i])
            j=f[j];
        if(T[j+1]==T[i])
            j++;
        f[i]=j;
    }
}
  • 最大公共前后缀->得到最小循环子串（这里原串可以是不完整的）
  • 最长前后缀，最短前后缀，重合前后缀，不重合前后缀的递推相关问题注意优化，跳fail的时候，不一定每次都从当前位置往前跳，类比kmp的原理可以考虑能不能从上一位遗留的jj 更新