记录编号	377699	评测结果	A
题目名称	[POJ 3461] 乌力波	最终得分	100
用户昵称	Sky_miner	是否通过	通过
代码语言	C++	运行时间	0.055 s
提交时间	2017-03-01 21:22:10	内存使用	3.49 MiB

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
inline void read(int &x){
	x=0;char ch;bool flag = false;
	while(ch=getchar(),ch<'!');if(ch == '-') ch=getchar(),flag = true;
	while(x=10*x+ch-'0',ch=getchar(),ch>'!');if(flag) x=-x;
}
const int maxn = 20010;
int ch[maxn][26],nodecnt;
int f[maxn],last[maxn];
bool ed[maxn];
#define id(x) (x - 'A')
void insert(char *s){
	int nw = 0,n = strlen(s);
	for(int i=0;i<n;++i){
		if(ch[nw][id(s[i])] == 0) ch[nw][id(s[i])] = ++nodecnt;
		nw = ch[nw][id(s[i])];
	}ed[nw] = true;
}
int q[maxn],l,r;
void build(){
	f[0] = 0;l = 0;r = -1;
	for(int i=0;i<26;++i){
		if(ch[0][i]){
			last[ch[0][i]] = f[ch[0][i]] = 0;
			q[++r] = ch[0][i];
		}
	}
	while(l <= r){
		int u = q[l++];
		for(int i=0;i<26;++i){
			int v = ch[u][i];
			if(!v){
				ch[u][i] = ch[f[u]][i];
				continue;
			}q[++r] = v;
			int x = f[u];
			while(x && !ch[x][i]) x = f[x];
			f[v] = ch[x][i];
			last[v] = ed[f[v]] ? f[v] : last[f[v]];
		}
	}
}
int find(char *s){
	int n = strlen(s),nw = 0;
	int ret = 0;
	for(int i = 0;i<n;++i){
		nw = ch[nw][id(s[i])];
		if(ed[nw] || last[nw]){
			if(ed[nw]) ++ ret;
			int x = nw;
			while(last[x]) ++ ret,x = last[x];
		}
	}
	return ret;
}
char s[10010],t[1000010];
inline void work(){
	memset(ch,0,sizeof ch);
	memset(ed,0,sizeof ed);
	memset(f,0,sizeof f);
	memset(last,0,sizeof last);
	nodecnt = 0;
	scanf("%s",s);scanf("%s",t);
	insert(s);build();
	printf("%d\n",find(t));
}
int main(){
	freopen("oulipo.in","r",stdin);
	freopen("oulipo.out","w",stdout);
	int T;read(T);
	while(T--) work();
	getchar();getchar();
	return 0;
}
/*
1
ASKJASDASDASDSADASKJDKJASNCKJASLKASJDLKJASNCKJNASKJALSCKJNASKLJFBIEUBCASBKCASBNKDJNASKLNCASLKCVBEVKALJSDKLASCKJASBNKJASNCKJSANLDBLKJBASDJHSAKLJDHKASJHDLJAKSHFIWUQHDIUABCKJASBLAKJSXNLKJAFLIWEGFKLASDHLKSAJCHLIWBCLKJABWDLKJAS
KJASAKSASDLKAJSKAJSASGYDKAJSGDLKJAGHWSJKLBKJASCBKAJSBCIUWBCILDGVLWKJBDKLAUSBCLKUAWGDIUALCBUKAGBLKJASGBCASKJLGBWCLIDHKJJKJBASKJNJCKSAASDASDDDDDDDDDDDDDDDDDDDDDDDDDDDDASDADASDAJHGKJASHDHWKJBASCKGAIOUDGASKUHLKASJCHBKAJSDBKWLUNXAUHYIEVDJAGCVKJXHOAWHDLWVDASCASDBHASKJHCSAHICUGHJKASBHIUASHCJBCBTD$RASCJNACGWUCSBCYSXJKHDJKSCISNUGUSDJASHKJASHDKJAGDLASKGBAKSJDHKAJSDGHLIWQUBCKJALSVBFIWUBAILSHDBLAICHLKJSNKJASCNOIUAGFIHKGBOLAGBLKJSCBLIDGBWUDGBWUIFGBLAWIUGBLKASJDHLKASJDHLASKJDHLKASJDHLASKJDHLASKJDHLASKJDHALSKJFSKAJGFWEHDIUQYOQWUIEYOIQUWGHDGSAJKCBZXNC<ADWIU
 */