COJ 0999 WZJ的数据结构（负一）

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'组成

题解：感人至深！

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cmath>
 4 #include<algorithm>
 5 #include<queue>
 6 #include<cstring>
 7 #define PAU putchar(' ')
 8 #define ENT putchar('
')
 9 using namespace std;
10 const int maxn=1000000+10,inf=-1u>>1,sig=2,maxnode=maxn;
11 struct node{node*tx[sig],*fail;int x;node(){x=0;}}ac[maxnode],*nodecnt=ac,*root=nodecnt++;
12 struct ted{int x,y;ted*nxt;}adj[maxn],*ms=adj,*fch[maxn],adj2[maxn],*ms2=adj2,*fch2[maxn];
13 void add(int x,int v){*ms=(ted){x,v,fch[x]};fch[x]=ms++;return;}
14 void add2(int x,int y){*ms2=(ted){x,y,fch2[x]};fch2[x]=ms2++;return;}
15 int num[maxn],ans[maxn];
16 void insert(char*s,int v){
17     node*x=root;
18     for(int i=0;s[i];i++){
19         int c=s[i]-'a';
20         if(!x->tx[c]) x->tx[c]=nodecnt++;
21         x=x->tx[c];
22     } add(x-ac,v);return;
23 }
24 void getfail(){
25     queue<node*>Q;for(int c=0;c<sig;c++)if(root->tx[c])Q.push(root->tx[c]),root->tx[c]->fail=root;
26     while(!Q.empty()){
27         node*x=Q.front();Q.pop();
28         for(int c=0;c<sig;c++)if(x->tx[c]){
29             node*p=x->fail;while(p&&!p->tx[c])p=p->fail;if(!p)p=root;
30             x->tx[c]->fail=p->tx[c]?p->tx[c]:root;Q.push(x->tx[c]);
31         }
32     } return;
33 }
34 void dfs(node*x){
35     for(ted*e=fch2[x-ac];e;e=e->nxt) dfs(e->y+ac),num[x-ac]+=num[e->y];
36 }
37 int query(char*s){
38     for(int i=1;i<=nodecnt-ac-1;i++) add2(ac[i].fail-ac,i);
39     node*x=root;
40     for(int i=0;s[i];i++){
41         int c=s[i]-'a';
42         while(x&&!x->tx[c]) x=x->fail;if(!x)x=root;
43         x=x->tx[c]?x->tx[c]:root;num[x-ac]++;
44     } dfs(root);
45     for(int i=nodecnt-ac-1;i;i--)
46         for(ted*e=fch[i];e;e=e->nxt)
47             ans[e->y]=num[i];
48 }
49 inline int read(){
50     int x=0,sig=1;char ch=getchar();
51     while(!isdigit(ch)){if(ch=='-') sig=-1;ch=getchar();}
52     while(isdigit(ch)) x=10*x+ch-'0',ch=getchar();
53     return x*=sig;
54 }
55 inline void write(int x){
56     if(x==0){putchar('0');return;}if(x<0) putchar('-'),x=-x;
57     int len=0,buf[15];while(x) buf[len++]=x%10,x/=10;
58     for(int i=len-1;i>=0;i--) putchar(buf[i]+'0');return;
59 }
60 char s[maxn];
61 int n;
62 void init(){
63     n=read();
64     for(int i=1;i<=n;i++) scanf("%s",s),insert(s,i);
65     getfail();
66     scanf("%s",s);query(s);
67     for(int i=1;i<=n;i++) write(ans[i]),ENT;
68     return;
69 }
70 void work(){
71     return;
72 }
73 void print(){
74     return;
75 }
76 int main(){
77     init();work();print();return 0;
78 }