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
1
0
1 2
解题思路：
1、AC自动机
首先，我是从来不用AC自动机的，直到看到了这道题。
Trie图构建时需要承受枚举字符集的复杂度，在匹配{a~z}时还只是一个26的常数在这道题变得不可承受。
所以就不能进行图没有儿子时的构建。
那么就是AC自动机了。
map存儿子。
vector存名字。
很少使用STL选手当场死亡。
向dalao请教map枚举元素的方法。
结果一直WA
最后才知道可能会有重复的询问QAQ拿vector存一下。
致敬hzwer学长·。
代码：
#include<map>
#include<queue>
#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
char xB[<<],*xS=xB,*xTT=xB;
#define getc() (xS==xTT&&(xTT=(xS=xB)+fread(xB,1,1<<15,stdin),xS==xTT)?0:*xS++)
#define isd(c) (c>='0'&&c<='9')
inline int read(){
char xchh;
int xaa;
while(xchh=getc(),!isd(xchh));(xaa=xchh-'');
while(xchh=getc(),isd(xchh))xaa=xaa*+xchh-'';
return xaa;
}
using std::map;
using std::queue;
using std::vector;
typedef unsigned int uit;
struct trnt{
map<int,int>ch;
int fl;
vector<int>fin;
int vis;
}tr[];
struct idt{
int la,lb;
vector<int>a;
vector<int>b;
int ans;
void Ins(void)
{
scanf("%d",&la);
for(int i=;i<=la;i++)
{
int tt;
scanf("%d",&tt);
a.push_back(tt);
}
scanf("%d",&lb);
for(int i=;i<=lb;i++)
{
int tt;
scanf("%d",&tt);
b.push_back(tt);
}
return ;
}
}cat[];
int num[];
bool usd[];
int n,m;
int siz;
int len;
queue<int>Q;
vector<int>hre;
void Insert(int k)
{
int len;
int c;
int root=;
scanf("%d",&len);
for(int i=;i<=len;i++)
{
scanf("%d",&c);
if(tr[root].ch.find(c)==tr[root].ch.end())
tr[root].ch[c]=++siz;
root=tr[root].ch[c];
}
tr[root].fin.push_back(k);
return ;
}
void Build(void)
{
int root=;
for(map<int,int>::iterator j=tr[root].ch.begin();j!=tr[root].ch.end();j++)
{
int sn=j->second;
tr[sn].fl=;
Q.push(sn);
}
while(!Q.empty())
{
root=Q.front();
Q.pop();
for(map<int,int>::iterator j=tr[root].ch.begin();j!=tr[root].ch.end();j++)
{
int i=j->first;
int sn=j->second;
int nxt=tr[root].fl;
while(nxt&&tr[nxt].ch.find(i)==tr[nxt].ch.end())
nxt=tr[nxt].fl;
if(tr[nxt].ch.find(i)!=tr[nxt].ch.end())
nxt=tr[nxt].ch[i];
tr[sn].fl=nxt;
Q.push(sn);
}
}
return;
}
void Query(int p)
{
int root;
root=;
for(uit i=;i<cat[p].a.size();i++)
{
int c=cat[p].a[i];
while(root&&tr[root].ch.find(c)==tr[root].ch.end())
root=tr[root].fl;
if(tr[root].ch.find(c)!=tr[root].ch.end())
{
root=tr[root].ch[c];
int nxt=root;
while(nxt)
{
if(tr[nxt].vis==p)
break;
tr[nxt].vis=p;
for(uit l=;l<tr[nxt].fin.size();l++)
{
int f=tr[nxt].fin[l];
if(!usd[f])
{
usd[f]=true;
hre.push_back(f);
cat[p].ans++;
num[f]++;
}
}
nxt=tr[nxt].fl;
}
}
}
root=;
for(uit i=;i<cat[p].b.size();i++)
{
int c=cat[p].b[i];
while(root&&tr[root].ch.find(c)==tr[root].ch.end())
root=tr[root].fl;
if(tr[root].ch.find(c)!=tr[root].ch.end())
{
root=tr[root].ch[c];
int nxt=root;
while(nxt)
{
if(tr[nxt].vis==p)
break;
tr[nxt].vis=p;
for(uit l=;l<tr[nxt].fin.size();l++)
{
int f=tr[nxt].fin[l];
if(!usd[f])
{
usd[f]=true;
hre.push_back(f);
cat[p].ans++;
num[f]++;
}
}
nxt=tr[nxt].fl;
}
}
}
for(uit i=;i<hre.size();i++)
usd[hre[i]]=false;
hre.clear();
return ;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)
cat[i].Ins();
for(int i=;i<=m;i++)
Insert(i);
Build();
for(int i=;i<=n;i++)
Query(i);
for(int i=;i<=m;i++)
printf("%d\n",num[i]);
for(int i=;i<=n;i++)
printf("%d ",cat[i].ans);
return ;
}
2.广义后缀自动机
只需要先建广义后缀自动机，在pre节点上打好标记，在查询时查询节点的标记就好了。 第二问只需在询问结束节点打标记遍历子串就好了。
代码：
#include<map>
#include<cstdio>
#include<cstring>
#include<algorithm>
struct sant{
std::map<int,int>tranc;
int len;
int pre;
}s[];
struct pnt{
int wgt;
int vis;
int tms;
}p[];
int cnt;
int siz;
int fin;
int n,m;
int lenfname[];
int lensname[];
int str[];
void Insert(int c)
{
int nwp,nwq,lsp,lsq;
nwp=++siz;
s[nwp].len=s[fin].len+;
for(lsp=fin;lsp&&(s[lsp].tranc.find(c)==s[lsp].tranc.end());lsp=s[lsp].pre)
s[lsp].tranc[c]=nwp;
if(!lsp)
s[nwp].pre=;
else{
lsq=s[lsp].tranc[c];
if(s[lsq].len==s[lsp].len+)
s[nwp].pre=lsq;
else{
nwq=++siz;
s[nwq]=s[lsq];
s[nwq].len=s[lsp].len+;
s[nwp].pre=s[lsq].pre=nwq;
while((s[lsp].tranc.find(c)!=s[lsp].tranc.end())&&s[lsp].tranc[c]==lsq)
{
s[lsp].tranc[c]=nwq;
lsp=s[lsp].pre;
}
}
}
fin=nwp;
return ;
}
void mark(int plc,int times)
{
if(!plc)
return ;
if(p[plc].vis==times)
return ;
p[plc].vis=times;
p[plc].wgt++;
mark(s[plc].pre,times);
return ;
}
int take(int plc,int times)
{
if(!plc)
return ;
if(p[plc].vis==times)
return ;
p[plc].vis=times;
return p[plc].tms+take(s[plc].pre,times);
}
int main()
{
fin=++siz;
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)
{
fin=;
scanf("%d",&lenfname[i]);
for(int j=;j<=lenfname[i];j++)
{
cnt++;
scanf("%d",&str[cnt]);
Insert(str[cnt]);
}
fin=;
scanf("%d",&lensname[i]);
for(int j=;j<=lensname[i];j++)
{
cnt++;
scanf("%d",&str[cnt]);
Insert(str[cnt]);
}
}
cnt=;
for(int i=;i<=n;i++)
{
int root;
root=;
for(int j=;j<=lenfname[i];j++)
{
cnt++;
root=s[root].tranc[str[cnt]];
mark(root,i);
}
root=;
for(int j=;j<=lensname[i];j++)
{
cnt++;
root=s[root].tranc[str[cnt]];
mark(root,i);
}
}
for(int i=;i<=m;i++)
{
int len;
int tmp;
scanf("%d",&len);
int root=;
for(int j=;j<=len;j++)
{
scanf("%d",&tmp);
if(!root)
continue;
if(s[root].tranc.find(tmp)!=s[root].tranc.end())
root=s[root].tranc[tmp];
else
root=;
}
printf("%d\n",p[root].wgt);
p[root].tms++;
}
cnt=;
for(int i=;i<=n;i++)
{
int ans=;
int root;
root=;
for(int j=;j<=lenfname[i];j++)
{
cnt++;
root=s[root].tranc[str[cnt]];
ans+=take(root,i+n);
}
root=;
for(int j=;j<=lensname[i];j++)
{
cnt++;
root=s[root].tranc[str[cnt]];
ans+=take(root,i+n);
}
printf("%d ",ans);
}
puts("");
return ;
}