| WZJ的数据结构（负一） |
| 难度级别：D； 运行时间限制：1000ms； 运行空间限制：262144KB； 代码长度限制：2000000B |
|
试题描述
|
|
输入N个模板串Pi和文本串T，输出每个模板串Pi在T中出现了多少次。
|
|
输入
|
|
第一行为一个正整数N。
接下来N行为Pi。 最后一行为T |
|
输出
|
|
输出N行，第i行为模板串Pi在T中出现的次数。
|
|
输入示例
|
|
5
a ab ba aba a ababababa |
|
输出示例
|
|
5
4 4 4 5 |
|
其他说明
|
|
1<=sigma(|Pi|)<=1000000
1<=|T|<=1000000 保证Pi与T只由小写字母'a'或'b'组成 |
题解：感人至深！
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<queue>
#include<cstring>
#define PAU putchar(' ')
#define ENT putchar('\n')
using namespace std;
const int maxn=+,inf=-1u>>,sig=,maxnode=maxn;
struct node{node*tx[sig],*fail;int x;node(){x=;}}ac[maxnode],*nodecnt=ac,*root=nodecnt++;
struct ted{int x,y;ted*nxt;}adj[maxn],*ms=adj,*fch[maxn],adj2[maxn],*ms2=adj2,*fch2[maxn];
void add(int x,int v){*ms=(ted){x,v,fch[x]};fch[x]=ms++;return;}
void add2(int x,int y){*ms2=(ted){x,y,fch2[x]};fch2[x]=ms2++;return;}
int num[maxn],ans[maxn];
void insert(char*s,int v){
node*x=root;
for(int i=;s[i];i++){
int c=s[i]-'a';
if(!x->tx[c]) x->tx[c]=nodecnt++;
x=x->tx[c];
} add(x-ac,v);return;
}
void getfail(){
queue<node*>Q;for(int c=;c<sig;c++)if(root->tx[c])Q.push(root->tx[c]),root->tx[c]->fail=root;
while(!Q.empty()){
node*x=Q.front();Q.pop();
for(int c=;c<sig;c++)if(x->tx[c]){
node*p=x->fail;while(p&&!p->tx[c])p=p->fail;if(!p)p=root;
x->tx[c]->fail=p->tx[c]?p->tx[c]:root;Q.push(x->tx[c]);
}
} return;
}
void dfs(node*x){
for(ted*e=fch2[x-ac];e;e=e->nxt) dfs(e->y+ac),num[x-ac]+=num[e->y];
}
int query(char*s){
for(int i=;i<=nodecnt-ac-;i++) add2(ac[i].fail-ac,i);
node*x=root;
for(int i=;s[i];i++){
int c=s[i]-'a';
while(x&&!x->tx[c]) x=x->fail;if(!x)x=root;
x=x->tx[c]?x->tx[c]:root;num[x-ac]++;
} dfs(root);
for(int i=nodecnt-ac-;i;i--)
for(ted*e=fch[i];e;e=e->nxt)
ans[e->y]=num[i];
}
inline int read(){
int x=,sig=;char ch=getchar();
while(!isdigit(ch)){if(ch=='-') sig=-;ch=getchar();}
while(isdigit(ch)) x=*x+ch-'',ch=getchar();
return x*=sig;
}
inline void write(int x){
if(x==){putchar('');return;}if(x<) putchar('-'),x=-x;
int len=,buf[];while(x) buf[len++]=x%,x/=;
for(int i=len-;i>=;i--) putchar(buf[i]+'');return;
}
char s[maxn];
int n;
void init(){
n=read();
for(int i=;i<=n;i++) scanf("%s",s),insert(s,i);
getfail();
scanf("%s",s);query(s);
for(int i=;i<=n;i++) write(ans[i]),ENT;
return;
}
void work(){
return;
}
void print(){
return;
}
int main(){
init();work();print();return ;
}