[POJ 3461]Oulipo

danihao123 posted @ 2016年8月28日 21:42 in 题解 with tags POJ KMP , 173 阅读
转载请注明出处:http://danihao123.is-programmer.com/

字符串搜索提……同时是KMP模板提……

注意啊变量别重名,结果会很壮观的(大吐核)。

代码:

#include <cstdio>
#include <cstring>
const int maxn=1000005,maxm=10005;
char P[maxm],T[maxn];
int f[maxm];
int n,m;
inline void MakeFail(){
    register int i,j;
    f[0]=f[1]=0;
    for(i=1;i<m;i++){
        j=f[i];
        while(j && P[j]!=P[i])
            j=f[j];
        f[i+1]=(P[j]==P[i]?j+1:0);
    }
}
inline int KMP(){
    register int i,j,ans=0;
    n=strlen(T);
    m=strlen(P);
    MakeFail();
    j=0;
    for(i=0;i<n;i++){
        while(j && P[j]!=T[i])
            j=f[j];
        if(P[j]==T[i])
            j++;
        if(j==m)
            ans++;
    }
    return ans;
}
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        scanf("%s%s",P,T);
        printf("%d\n",KMP());
    }
    return 0;
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter