bzoj 2754: [SCOI2012]喵星球上的点名

.

题意：序列匹配
题解：AC自动机
因为这题匹配的不是字母，而是数，所以要把trie里要用map存儿子。
代码：

#include<bits/stdc++.h>
using namespace std;

int n,m,num=0,v[100010],tt=0,ans1[50010],ans2[20010];
struct trie
{
    map<int,int>s;
    int fail;
    vector<int>c;
}tr[100010];
vector<int>a[20010];

void in(vector<int>&a)
{
    int l;
    scanf("%d",&l);
    for(int i=0;i<l;i++)
    {
        int x;
        scanf("%d",&x);
        a.push_back(x);
    }
}
void ins(vector<int>x,int y)
{
    int now=0;
    for(int i=0;i<x.size();i++)
    {
        if(!tr[now].s[x[i]])
        tr[now].s[x[i]]=++num;
        now=tr[now].s[x[i]];
    }
    tr[now].c.push_back(y);
}
inline void bf()
{
    queue<int>q;
    tr[0].fail=0;
    for(map<int,int>::iterator it=tr[0].s.begin();it!=tr[0].s.end();it++)
    q.push(it->second);
    while(!q.empty())
    {
        int x=q.front();
//        printf("%d %d\n",x,tr[x].fail);
        for(map<int,int>::iterator it=tr[x].s.begin();it!=tr[x].s.end();it++)
        {
            int i=it->second,j=tr[x].fail;
            while(j&&!tr[j].s.count(it->first))
            j=tr[j].fail;
            if(tr[j].s.count(it->first))
            j=tr[j].s[it->first];
            tr[i].fail=j;
            q.push(i);
        }
        q.pop();
    }
}
int wk(vector<int>&a)
{
    int now=0,s=0;
    tt++;
    for(int i=0;i<a.size();i++)
    {
        while(now&&!tr[now].s.count(a[i]))
        now=tr[now].fail;
        if(tr[now].s.count(a[i]))
        now=tr[now].s[a[i]];
//        printf("%d ",now);
        for(int j=now;j;j=tr[j].fail)
        if(v[j]!=tt)
        {
            v[j]=tt;
            for(int k=0;k<tr[j].c.size();k++)
            {
                ans1[tr[j].c[k]]++;
                s++;
            }
        }
        else
        break;
    }
//    puts("");
    return s;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        in(a[i]);
        a[i].push_back(-1);
        in(a[i]);
    }
    for(int i=0;i<m;i++)
    {
        vector<int>tmp;
        in(tmp);
        ins(tmp,i);
    }/*
    for(int i=0;i<=num;i++)
    {
        printf("i:%d\n",i);
        printf("c:");
        for(auto j:tr[i].c)
        printf("%d ",j);
        puts("\ns:");
        for(auto j:tr[i].s)
        printf("%d %d\n",j.first,j.second);
        puts("===");
    }*/
    bf();
    for(int i=1;i<=n;i++)
    {
        ans2[i]+=wk(a[i]);
    }
    for(int i=0;i<m;i++)
    printf("%d\n",ans1[i]);
    for(int i=1;i<=n;i++)
    printf("%d%c",ans2[i],i<n?' ':'\n');
}