HDU-1686- Oulipo KMP匹配

HDU-1686- Oulipo

PJ的女朋友是一个书法家，喜欢写一些好看的英文书法。有一天PJ拿到了她写的纸条，暗示要送给他生日礼物。PJ想知道自己想要的礼物是不是就是她送的，于是想看看自己想要的在纸条中出现了多少次。

Input
第一行输入一个整数代表数据的组数
每组数据第一行一个字符串 W代表PJ想要的礼物, 包含英语字符 {‘A’, ‘B’, ‘C’, …, ‘Z’}, 并且字符串长度满足 1 ≤|W| ≤ 10,000 (|W| 代表 W字符串的长度). 接下来一行一个字符串 T代表女朋友的纸条, 也包含英语字符 {‘A’, ‘B’, ‘C’, …, ‘Z’}, 满足 |W| ≤ |T| ≤ 1,000,000.
Output 输出一行一个整数代表 W 在T中出现的次数.

Sample Input :
3
BAPC
BAPC
AZA
AZAZAZA
VERDI
AVERDXIVYERDIAN

Sample Output:
1
3
0

解题思路：题目要求求出模式串P在母串S中出现次数，注意点：模式串AZA在母串AZAZA中算出现两次 ；因为这题数据范围比较大，很明显用暴力算法是过不去的，所以这题是一道KMP字符串匹配模版题，所以详解请见KMP字符串匹配算法及KMP优化代码
代码如下：

#include<stdio.h>
#include<cstring>
#include<iostream>
using namespace std;
const int maxn=1e6+5; 
char s[maxn],t[maxn];
int slen,tlen;
int nex[maxn];//nex数组大小和短串一致
int ans,a,b,c,d,n,m;
inline void get_nex(){
    int j=-1;//影响next[0] 
    for (int i=0;i<tlen;i++){
        while(t[i]!=t[j+1] && j!=-1)j=nex[j];
        if (t[i]==t[j+1] && i!=0) j++;
        nex[i]=j;
	}
}
inline void kmp(){
    int j=-1;
    for (int i=0;i<slen;i++){
        while(s[i]!=t[j+1] && j!=-1) j=nex[j];
        if (s[i]==t[j+1]) j++;
        if (j==tlen-1)ans++,j=nex[j];
    }
}
int main(){
    scanf("%d",&n);
    while(n--){
        ans=0;
        scanf("%s",t);
        scanf("%s",s);
        slen=strlen(s);
        tlen=strlen(t);//这两个长度应该设为全局变量最开始时求出，不能用一次求一次
        get_nex();
        //for(int i=0;i<tlen;i++)printf("%d ",nex[i]);
		//printf("\n"); 
        kmp();		//kmp函数 
        printf("%d\n",ans);
    }
}