hdu(1686)——Oulipo

题意：

给你两个串A,B，让你求A串在B串中的出现次数。

思路：

kmp。。。但是一开始没想通，其实只要在求next数组时，最后把len-1那个位置的next值也求出来就好了，因为我们知道了最后一个字母对应的最大公共前缀后缀，那么我们就可以在第二个样例的时候当完成第一次匹配后，我们知道文本串后一位应该和模式串的那一位去匹配了。其实说白了就是把最后一个字母的最大公共前缀后缀也求出来了嘛，这样我们也就可以知道它下一个应该去匹配哪个字母了。

AZA

AZAZAZA

AZA的next值为：

-1 0 0 1

当第一次匹配完时，j=next[j]=next[3]=1; 所以文本串中a[3]='Z'此时就应该匹配模式串中的b[1]='Z'了，很巧妙把~~~

#include<cstdio>
#include<cstring>
#include<map>
#include<set>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
#include<iostream>
#include<time.h>
using namespace std;
typedef __int64 ll;
typedef unsigned __int64 ULL;
#define pi acos(-1.0)
#define Ex exp(1.0)
#define inf 99999999
#define maxn 1000010
char a[10010],b[maxn];
int next1[10010];
int n,m,idx;
void getnext(){
    int j=0,k=-1;
    int len=strlen(a);
    memset(next1,-1,sizeof(next1));
    while(j<len){
        if(k==-1||a[j]==a[k]){
            ++k;
            ++j;
            next1[j]=k;
        }
        else k=next1[k];
    }
}
int kmp(){
    int i=0,j=0;
    int num=0;
    int l1=strlen(a),l2=strlen(b);
    while(j<l2){
        if(i==-1||a[i]==b[j]){
            ++i;
            ++j;
        }
        else i=next1[i];
        if(i==l1){
            i=next1[i];
            num++;
        }
    }
    return num;
}
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        scanf("%s%s",a,b);
        getnext();
        int num=kmp();
        printf("%d\n",num);
    }
    #ifndef ONLINE_JUDGE
    system("pause");
    #endif
    return 0;
}
/*
1
AZA
AZAZAZA
*/