kmp

[c++]代码库

/*
    2016年4月28日10:27:36
    kmp
    注意重复的也算
    p：AZA
    t：AZAZAZA

    ans = 3;
*/
#include<stdio.h>
#include<string.h>

const int maxn = 1e6 + 5;

char p[10005];
int next[10005];
char t[maxn];

void makenext()
{
    int m = strlen(p);
    next[0] = 0;
    for(int q = 1,k = 0;q < m;q++)
    {
        while(k > 0 && p[q] != p[k])
            k = next[k-1];          //跳到上一个前缀
        if(p[q] == p[k])
            k++;
        next[q] = k;
    }
}
int kmp()
{
    int ans = 0;
    int m = strlen(p);
    int n = strlen(t);
    for(int i = 0,q = 0;i < n;i++)
    {
        while(q > 0 && p[q] != t[i])
            q = next[q-1];
        if(p[q] == t[i])
            q++;
        if(q == m)
        {
            ans++;
            q = next[q-1];  //如果重复的不算的话，q = 0;和上面的k = next[k-1];比较看一下
        }
    }
    return ans;
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%s",p);
        scanf("%s",t);
        makenext();
        printf("%d\n",kmp());
    }
    return 0;
}
/*
3
BAPC
BAPC
AZA
AZAZAZA
VERDI
AVERDXIVYERDIAN

1
3
0
*/

[源代码打包下载]