hdu1686 Oulipo kmp

题目传送门

思路：kmp模板，稍微修改下

　　

#include<bits/stdc++.h>
#define clr(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
const int maxn=1000100;
char p[maxn],t[maxn];
int f[maxn],n,m,ans;
void fail(){
    f[0]=-1;
    for(int j=1;j<m;j++)
    {
        for(int i=f[j-1];;i=f[i]){
            if(p[j]==p[i+1]){
                f[j]=i+1;
                break;
            }else if(i==-1){
                f[j]=-1;
                break;
            }
        }
    }
}
int kmp(){
    fail();
    int i=0,j=0;
    while(i<n&&j<m)
    {
        if(t[i]==p[j]){
            i++,j++;
            if(j==m){
                ans++;
                j=f[j-1]+1;//如果匹配完了，在接下来的位置还能匹配的话，那么还是回到前缀 
            }
        }else if(j==0){
            i++;
        }else{
            j=f[j-1]+1;
        }
    }
    return ans;
}
int main(){
    int T;
    cin>>T;
    while(T--)
    {
        scanf("%s",p);
        scanf("%s",t);
        m=strlen(p),n=strlen(t);
        ans=0;
        printf("%d
",kmp());
    }
}