记录编号	379402	评测结果	A
题目名称	[POJ 3461] 乌力波	最终得分	100
用户昵称	AntiLeaf	是否通过	通过
代码语言	C++	运行时间	0.050 s
提交时间	2017-03-06 13:59:32	内存使用	3.39 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=20010;
void expand(int);
int root,last,cnt=0,val[maxn]={0},par[maxn]={0},go[maxn][26]={{0}};
char s[1000010],t[maxn>>1];
int T,n,m,ans;
int main(){
	freopen("oulipo.in","r",stdin);
	freopen("oulipo.out","w",stdout);
	scanf("%d",&T);
	while(T--){
		fill(val,val+cnt+1,0);
		fill(par,par+cnt+1,0);
		for(int i=0;i<=cnt;i++)memset(go[i],0,sizeof(go[i]));
		root=last=cnt=1;
		scanf("%s%s",t,s);
		n=strlen(s);
		m=strlen(t);
		for(int i=0;i<m;i++)expand(t[i]-'A');
		ans=0;
		for(int i=0,x=root,len=0;i<n;i++){
			while(x&&!go[x][s[i]-'A']){
				x=par[x];
				len=val[x];
			}
			if(!x){
				x=root;
				len=0;
			}
			else{
				x=go[x][s[i]-'A'];
				len++;
			}
			if(len==m)ans++;
		}
		printf("%d\n",ans);
	}
	return 0;
}
void expand(int c){
	int p=last,np=++cnt;
	val[np]=val[p]+1;
	while(p&&!go[p][c]){
		go[p][c]=np;
		p=par[p];
	}
	if(!p)par[np]=root;
	else{
		int q=go[p][c];
		if(val[q]==val[p]+1)par[np]=q;
		else{
			int nq=++cnt;
			val[nq]=val[p]+1;
			memcpy(go[nq],go[q],sizeof(go[q]));
			par[nq]=par[q];
			par[np]=par[q]=nq;
			while(p&&go[p][c]==q){
				go[p][c]=nq;
				p=par[p];
			}
		}
	}
	last=np;
}