【bzoj2754】【scoi2012】【喵星球上的点名】【AC自动机+map】

【数据范围】 

 对于30%的数据，保证： 

1<=N,M<=1000，喵星人的名字总长不超过4000，点名串的总长不超过2000。

对于100%的数据，保证：

1<=N<=20000，1<=M<=50000，喵星人的名字总长和点名串的总长分别不超过100000，保证喵星人的字符串中作为字符存在的数不超过10000。

题解：

         因为字符集比较大，我们可以把AC自动机上的每个点搞成map.

         每次沿着fail指针暴力往上走即可。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<map>
#define N 100010
using namespace std;
int L,n,m,x,y,ans1[N],ans2[N],f[N],vis[N];
vector<int>a[N],pos[N],A,B;
map<int,int>ch[N];
struct use{int cnt,fail[N],q[N];use(){cnt=1;for (int i=-1;i<=10000;i++) ch[0][i]=1;}void insert(int x){scanf("%d",&L);int now=1;int t;for (int i=1;i<=L;i++){scanf("%d",&t);if (!ch[now][t]) ch[now][t]=++cnt;now=ch[now][t];}pos[now].push_back(x);}void build(){int h(0),t(1);fail[1]=0;q[0]=1;while (h!=t){int x=q[h++];for (map<int,int>::iterator i=ch[x].begin();i!=ch[x].end();i++){int tt=i->first,k=fail[x];while (!ch[k][tt]) k=fail[k];fail[i->second]=ch[k][tt];q[t++]=i->second; }	}}void update(int x,int k){for (int i=k;i;i=fail[i]){	 if (!vis[i]){vis[i]=1;A.push_back(i);for (int j=0;j<pos[i].size();j++)if(!f[pos[i][j]]){f[pos[i][j]]=1;B.push_back(pos[i][j]);ans1[pos[i][j]]++;ans2[x]++;}}}}void calc(int x){int k(1);for (int i=0;i<a[x].size();i++){int t=a[x][i];while (!ch[k][t]) k=fail[k];k=ch[k][t];update(x,k);}for(int i=0;i<A.size();i++)vis[A[i]]=0;for(int i=0;i<B.size();i++)f[B[i]]=0;A.clear();B.clear();}
}acm;
int main(){scanf("%d%d",&n,&m);for (int i=1;i<=n;i++){scanf("%d",&L);for (int j=1;j<=L;j++) scanf("%d",&x),a[i].push_back(x);a[i].push_back(-1);scanf("%d",&L);for (int j=1;j<=L;j++) scanf("%d",&x),a[i].push_back(x);}for (int i=1;i<=m;i++) acm.insert(i);acm.build();for (int i=1;i<=n;i++) acm.calc(i);for (int i=1;i<=m;i++) printf("%d\n",ans1[i]);for (int i=1;i<=n;i++){printf("%d",ans2[i]);if (i!=n) printf(" ");}
}