字符串KMP算法

讲解：http://blog.csdn.net/starstar1992/article/details/54913261

#include <bits/stdc++.h>
using namespace std;
char a[10005],b[10005];
int nxt[10005];
void get_nxt(int n)
{
    int p=0, q=-1;
    nxt[p]=q;
    while(p<n) {
        if(q==-1 || a[p]==a[q])
            nxt[p++]=q++;
        else q=nxt[q];
    }
}
int KMP(int na,int nb)
{
    get_nxt(na);
    int p=0, q=0, ans=0;
    while(p<nb) {
        if(q==-1 || b[p]==a[q])
            p++, q++;
        else q=nxt[q];
        if(q==na-1) ans++;
    }
    return ans;
}
int main()
{
    scanf("%s%s",a,b);
    int na=strlen(a), nb=strlen(b);
    printf("%d",KMP(na,nb));/// a串在b串中出现次数

    return 0;
}