2754: [SCOI2012]喵星球上的点名 Time Limit: 20 Sec Memory Limit: 128 MB Submit: 2246 Solved: 975 Description a180285幸运地被选做了地球到喵星球的留学生。他发现喵星人在上课前的点名现象非常有趣。 假设课堂上有N个喵星人，每个喵星人的名字由姓和名构成。喵星球上的老师会选择M个串来点名，每次读出一个串的时候，如果这个串是一个喵星人的姓或名的子串，那么这个喵星人就必须答到。 然而，由于喵星人的字码过于古怪，以至于不能用ASCII码来表示。为了方便描述，a180285决定用数串来表示喵星人的名字。 现在你能帮助a180285统计每次点名的时候有多少喵星人答到，以及M次点名结束后每个喵星人答到多少次吗？ Input
现在定义喵星球上的字符串给定方法： 先给出一个正整数L，表示字符串的长度，接下来L个整数表示字符串的每个字符。 输入的第一行是两个整数N和M。 接下来有N行，每行包含第i 个喵星人的姓和名两个串。姓和名都是标准的喵星球上的 字符串。 接下来有M行，每行包含一个喵星球上的字符串，表示老师点名的串。 Output
对于每个老师点名的串输出有多少个喵星人应该答到。 然后在最后一行输出每个喵星人被点到多少次。 Sample Input 2 3
6 8 25 0 24 14 8 6 18 0 10 20 24 0
7 14 17 8 7 0 17 0 5 8 25 0 24 0
4 8 25 0 24
4 7 0 17 0
4 17 0 8 25
Sample Output
2
1
0
1 2
【提示】
事实上样例给出的数据如果翻译成地球上的语言可以这样来看
2 3
izayoi sakuya
orihara izaya
izay
hara
raiz HINT
【数据范围】
对于30%的数据，保证：
1<=N,M<=1000，喵星人的名字总长不超过4000，点名串的总长不超过2000。
对于100%的数据，保证：
1<=N<=20000，1<=M<=50000，喵星人的名字总长和点名串的总长分别不超过100000，保证喵星人的字符串中作为字符存在的数不超过10000。
#include<iostream> #include<cstring> #include<cstdio> #include<vector> #include<queue> #include<map> using namespace std; #define N 20005 #define M 50005 #define NUM 10005 #define MAXN 1000005 vector<int> name[N][2]; vector<int> son[MAXN]; int cntnode=0,hash[M],ans[N],cnt[MAXN],siz[MAXN],vis[MAXN],n,m; int read(){ int r=0;char c=getchar(); while(c<'0'||c>'9')c=getchar(); while(c>='0'&&c<='9')r=r*10+c-'0',c=getchar(); return r; } struct node{ node* fail; map<int,node*>next; int idx; node(){ idx=0;fail=NULL; } }; struct AC_Tree{ node* root; void init(){ root = new node(); root->fail = root; root->idx = ++cntnode; } void Insert(int len,int id){ node *p=root; for(int k=1;k<=len;k++){ int x=read(); if(p->next[x] == NULL){ p->next[x] = new node(); p->next[x]->idx = ++cntnode; son[p->idx].push_back(x); } p = p->next[x]; } hash[id] = p->idx; siz[p->idx]++; } void build(){ queue<node*>q; for(int j=0,J=son[root->idx].size();j<J;j++){ int i=son[root->idx][j]; root->next[i]->fail = root; q.push(root->next[i]); } while(!q.empty()){ node *u=q.front();q.pop(); for(int j=0,J=son[u->idx].size();j<J;j++){ int i=son[u->idx][j]; node* v=u->next[i],*t=u->fail; while(t!=root && !t->next[i]){ t=t->fail; } v->fail = t->next[i] ? t->next[i] : root; q.push(v); } } } void solve(int x){ for(int k=0;k<2;k++){ node *p = root; for(int i=0,size=name[x][k].size();i<size;i++){ int c=name[x][k][i]; while(p!=root&&!p->next[c]) p=p->fail; if(p->next[c]) p=p->next[c]; node *cur=p; for(;cur!=root;cur = cur->fail){ if(vis[cur->idx] == x) continue; vis[cur->idx]=x; ans[x]+=siz[cur->idx]; cnt[cur->idx]++; } } } } }AC; int main(){ AC.init(); n=read();m=read(); for(int i=1;i<=n;i++) for(int j=0,l;j<2;j++){ l=read(); for(int k=1;k<=l;k++) name[i][j].push_back(read()); } for(int i=1;i<=m;i++){ int k=read(); AC.Insert(k,i); } AC.build(); for(int i=1;i<=n;i++) AC.solve(i); for(int i=1;i<=m;i++) printf("%d\n",cnt[hash[i]]); for(int i=1;i<n;i++) printf("%d ",ans[i]); printf("%d",ans[n]); }