BZOJ2754 SCOI2012喵星球上的点名

绝世好题。

正当我犹豫不决时，hzwer说：“MAP！！！”

没错这题大大的暴力，生猛的stl，贼基尔爽,,ԾㅂԾ,,

由于我们求点名在名字中的子串个数，所以将点名建AC自动机，记录节点属于哪次点名，每次带着这位同学的所有名字去里面扫，注意判重

复杂度20000*100000以及玄学的stl复杂度。

By：大奕哥

 #include<bits/stdc++.h>

 using namespace std;

 const int N=1e5+;

 int ans1[N],ans2[N],fail[N],n,m,cnt;

 map<int,int>t[N];

 vector<int>pos[N],a[N];

 queue<int>q;

 void build(int id)

 {

     int x,k;scanf("%d",&x);int now=;

     for(int i=;i<=x;++i)

     {

         scanf("%d",&k);

         if(!t[now][k])t[now][k]=++cnt;

         now=t[now][k];

     }

     pos[now].push_back(id);

 }

 void getfail()

 {

     for(map<int,int>::iterator i=t[].begin();i!=t[].end();++i)

     {

         int u=i->second;

         q.push(u);

         fail[u]=;

     }

     while(!q.empty())

     {

         int x=q.front();q.pop();

         for(map<int,int>::iterator i=t[x].begin();i!=t[x].end();++i)

         {

             int c=i->first,u=i->second;

             q.push(u);

             int k=fail[x];

             while(k&&!t[k][c])k=fail[k];

             fail[u]=t[k][c];

         }

     }

 }

 bool v[N],mark[N];

 vector<int>H,M;

 void get(int x,int p)

 {

     for(int i=p;i;i=fail[i])

     {

         if(v[i])return;

         v[i]=;H.push_back(i);

         for(int j=;j<pos[i].size();++j)

         if(!mark[pos[i][j]])

         {

             mark[pos[i][j]]=;

             ans1[pos[i][j]]++;

             ans2[x]++;

             M.push_back(pos[i][j]);

         }

     }

     return;

 }

 void find(int x,vector<int>g)

 {

     int ans=,now=,l=g.size();

     for(int i=;i<l;++i)

     {

         int c=g[i];

         while(now&&!t[now][c])now=fail[now];

         now=t[now][c];

         get(x,now);

     }

     for(int i=;i<H.size();++i)v[H[i]]=;

     for(int i=;i<M.size();++i)mark[M[i]]=;

     H.clear();M.clear();

     return;

 }

 int main()

 {

     scanf("%d%d",&n,&m);int x,k;

     for(int i=;i<=n;++i)

     {

         scanf("%d",&x);

         for(int j=;j<=x;++j)

         scanf("%d",&k),a[i].push_back(k);

         a[i].push_back(-);//添加非法字符防止姓和名连在一起成一个子串

         scanf("%d",&x);

         for(int j=;j<=x;++j)

         scanf("%d",&k),a[i].push_back(k);

     }

     for(int i=;i<=m;++i)build(i);

     getfail();

     for(int i=;i<=n;++i)

     find(i,a[i]);

     for(int i=;i<=m;++i)printf("%d\n",ans1[i]);

     for(int i=;i<n;++i)printf("%d ",ans2[i]);

     printf("%d",ans2[n]);

     return ;

 }