POJ3461：Oulipo——题解

http://poj.org/problem?id=3461

KMP板子，好久以前学过了，直接把板子粘上去即可。

#include<cstdio>
#include<cstring>
using namespace std;
char s1[1000001];
char s2[10001];
int nxt[10001]={0};
void getnext(int m){
    int j=0;
    for(int i=2;i<=m;i++){
    while(j!=0&&s2[j+1]!=s2[i])j=nxt[j];
    if(s2[j+1]==s2[i])j++;
    nxt[i]=j;
    }
    return;
}
int ans;
void KMP(int n,int m){
    int j=0;
    for(int i=1;i<=n;i++){
    while(j!=0&&s2[j+1]!=s1[i])j=nxt[j];
    if(s2[j+1]==s1[i])j++;
    if(j==m){
        ans++;
        j=nxt[j];
    }
    }
    return;
}
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
    ans=0;
    memset(nxt,0,sizeof(nxt));
    scanf("%s%s",s2+1,s1+1);
    int n=strlen(s1+1),m=strlen(s2+1);
    getnext(m);
    KMP(n,m);
    printf("%d
",ans);
    }
    return 0;
}