KMP小结

2024-08-31 18:54:31

1.

KMP模版：

代表题目：POJ 3641 Oulipo KMP http://blog.csdn.net/murmured/article/details/12871891

char P[MAXN],T[MAXM];

int f[MAXN],n,m,ans;

void getFail()

{

    f[0]=f[1]=0;

    int j;

    for(int i=1;i<n;i++)

    {

        j=f[i];

        while(j && P[i]!=P[j])

            j=f[j];  

        if(P[i]==P[j])

            j++;  

        f[i+1]=j;

    }

}  

void kmp()

{

    int j=0;

    for(int i=0;i<m;i++)

    {

        while(j && P[j] != T[i])

            j=f[j];  

        if( T[i]==P[j])

            j++;  

        if(j==n)

        {

            ans++;  

        }

    }

}

2.

KMP求周期

代表题目： POJ 2406 Power Strings KMP求周期http://blog.csdn.net/murmured/article/details/12868211

LA 3026 - Period KMP http://blog.csdn.net/murmured/article/details/12675953

HDU 3746 Cyclic Nacklace KMP http://blog.csdn.net/murmured/article/details/12859607

len%(len-next[i])==0

此字符串的最小周期就为len/(len-next[i]);

下面摘自http://www.cnblogs.com/wuyiqi/archive/2012/01/06/2314078.html

-----------------------

-----------------------

k m x j i

由上，next【i】=j，两段红色的字符串相等（两个字符串完全相等），s[k....j]==s[m....i]

设s[x...j]=s[j....i](xj=ji)

则可得，以下简写字符串表达方式

kj=kx+xj;

mi=mj+ji;

因为xj=ji，所以kx=mj，如下图所示

-------------

-------------

k m x j

看到了没，此时又重复上面的模型了，kx=mj，所以可以一直这样递推下去

所以可以推出一个重要的性质len-next[i]为此字符串的最小循环节(i为字符串的结尾)，另外如果len%(len-next[i])==0,此字符串的最小周期就为len/(len-next[i]);

3.

前缀后缀

字符查找过程中，会有一个状态值j,这个j表示s2已经匹配了s1多少个字符

HDU 2594 Simpsons’ Hidden Talents KMP http://blog.csdn.net/murmured/article/details/12867995

POJ 2752 Seek the Name, Seek the Fame http://blog.csdn.net/murmured/article/details/12870805

HDU 3336 Count the string KMP+DP http://blog.csdn.net/murmured/article/details/12858343

最新文章

热门文章