2754: [SCOI2012]喵星球上的点名
Time Limit: 20 Sec Memory Limit: 128 MBSubmit: 1921 Solved: 848
[Submit][Status][Discuss]
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
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。
Source
分析：
其实正解是后缀数组+主席树，但是听说AC自动机可以暴力水过去...
因为我们要求点名串是名字的子串，所以建出点名串的AC自动机，然后对于每一个名字暴力匹配，暴力沿着fail树向上找更新路径信息...
子节点太多？map大法好...
代码：
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<map>
//by NeighThorn
using namespace std;
const int maxm=100000+5;
int n,m,tot,head,tail,q[maxm],ans[maxm],sum[maxm],siz[maxm],vis[maxm],fail[maxm],node[maxm];
map<int,int> nxt[maxm];
vector<int> str[2][maxm],son[maxm];
inline int read(void){
char ch=getchar();int x=0;
while(!(ch>='0'&&ch<='9'))
ch=getchar();
while(ch>='0'&&ch<='9')
x=x*10+ch-'0',ch=getchar();
return x;
}
inline void insert(int id){
int len=read(),p=0;
for(int i=1,x;i<=len;i++){
x=read();
if(!nxt[p][x])
nxt[p][x]=++tot,son[p].push_back(x),fail[tot]=-1;
p=nxt[p][x];
}
node[id]=p;siz[p]++;
}
inline void buildACM(void){
head=0,tail=0,q[0]=0;
while(head<=tail){
int id=q[head++],p=-1;
for(int i=0;i<son[id].size();i++){
if(id){
p=fail[id];
while(p!=-1){
if(nxt[p][son[id][i]]){
fail[nxt[id][son[id][i]]]=nxt[p][son[id][i]];
break;
}
p=fail[p];
}
if(p==-1) fail[nxt[id][son[id][i]]]=0;
}
else
fail[nxt[id][son[id][i]]]=0;
q[++tail]=nxt[id][son[id][i]];
}
}
}
inline void solve(void){
for(int i=1,x,p;i<=n;i++)
for(int j=0;j<=1;j++){
p=0;
for(int k=0;k<str[j][i].size();k++){
x=str[j][i][k];
while(p&&!nxt[p][x]) p=fail[p];
if(nxt[p][x])
p=nxt[p][x];
int tmp=p;
while(tmp){
if(siz[tmp]&&vis[tmp]!=i)
ans[tmp]++,sum[i]+=siz[tmp],vis[tmp]=i;
tmp=fail[tmp];
}
}
}
}
signed main(void){
n=read();m=read();fail[0]=-1;
for(int i=1,x;i<=n;i++){
x=read();
for(int j=1;j<=x;j++)
str[0][i].push_back(read());
x=read();
for(int j=1;j<=x;j++)
str[1][i].push_back(read());
}
for(int i=1;i<=m;i++)
insert(i);
buildACM();solve();
for(int i=1;i<=m;i++)
printf("%d
",ans[node[i]]);
for(int i=1;i<n;i++)
printf("%d ",sum[i]);printf("%d
",sum[n]);puts("");
return 0;
}
By NeighThorn