KMP算法（字符串）

纯模板题：HDU1686

#include<cstdio>
#include<cstdlib>
#include<cstring>
#define INF 1000005

int next[INF];
char a[INF],b[INF];
void getnext(char *str)
{
    int j=0;
    int len=strlen(str);
    next[0]=0;
    for(int i=1;i<len;i++)
    {
        while(j>0&&str[i]!=str[j])
              j=next[j-1];
        if(str[i]==str[j])
            j++;
        next[i]=j;
    }
}

int kmp(char *str1,char *str2)
{
    int len1=strlen(str1),len2=strlen(str2); //str1是待匹配串，str2是匹配串
    int j=0,ans=0;
    for(int i=0;i<len2;i++)
    {
        if(str1[j]!=str2[i]&&j>0)
            j=next[j-1];
        if(str1[j]==str2[i])
            j++;
        if(j==len1) //相等说明找到子串
            ans++;
    }
    return ans;

}

int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%s",a);
        getnext(a);
        scanf("%s",b);
        int ans=kmp(a,b);
        printf("%d\n",ans);
    }
    return 0;
}

next数组的运用（HDU3746）

#include<cstdio>
#include<cstring>
#define INF 1000005

int next[INF];
char inp[INF];
void getnext(char *a,int n)
{
    int i=0,j=next[0]=-1;
    while(i<n)
    {
        while(j!=-1&&inp[i]!=inp[j])
            j=next[j];
        i++;j++;
        next[i]=j;
    }
}

int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%s",inp);
        int n=strlen(inp);
        getnext(inp,n);
        int ans=n-next[n];
        if(n!=ans&&n%ans==0) printf("0\n");
        else
        {
            ans=ans-next[n]%ans;
            printf("%d\n",ans);
        }
    }
    return 0;
}