[BZOJ2754/Luogu2336][SCOI2012]喵星球上的点名(AC自动机)

发布于 2018-03-20  70 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ2754/Luogu2336][SCOI2012]喵星球上的点名(AC自动机)

Description

a180285幸运地被选做了地球到喵星球的留学生。他发现喵星人在上课前的点名现象非常有趣。 假设课堂上有N个喵星人,每个喵星人的名字由姓和名构成。喵星球上的老师会选择M个串来点名,每次读出一个串的时候,如果这个串是一个喵星人的姓或名的子串,那么这个喵星人就必须答到。 然而,由于喵星人的字码过于古怪,以至于不能用ASCII码来表示。为了方便描述,a180285决定用数串来表示喵星人的名字。
现在你能帮助a180285统计每次点名的时候有多少喵星人答到,以及M次点名结束后每个喵星人答到多少次吗?

Tag

AC自动机

解决思路

对点名串建立AC自动机,然后分别把每一个喵星人的姓和名放进去匹配。注意,同一个喵星人的姓和名都匹配的时候只算一次匹配。
另外不好处理的是,由于字符集比较大,也有可能有重复元素,所以要用map存子节点,用id编号标记同样的点名串,避免出现多次转移。

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<map>
#include<vector>
#include<queue>
using namespace std;

#define ll long long
#define mem(Arr,x) memset(Arr,x,sizeof(Arr))

const int maxN=52010*2;
const int maxTrie=140000;
const int inf=2147483647;

class TrieData
{
public:
    int id,fail,cnt;
    map<int,int> Son;
    TrieData()
        {
            id=cnt=0;return;
        }
};

int n,m;
int nodecnt=0;
TrieData T[maxTrie];
vector<int> FName[maxN],LName[maxN];
queue<int> Queue;
int idcnt=0,Ans1[maxN],Ans2[maxN];
int Hist[maxN];
int NodeId[maxN];
map<int,int>::iterator iii;

void Insert(int id);
void GetFail();
void AhoCorasick(vector<int> V,int id);

int main()
{
    scanf("%d%d",&n,&m);
    //读入名字
    for (int i=1;i<=n;i++)
    {
        int l;scanf("%d",&l);
        for (int j=1;j<=l;j++){
            int a;scanf("%d",&a);
            FName[i].push_back(a);
        }
        scanf("%d",&l);
        for (int j=1;j<=l;j++){
            int a;scanf("%d",&a);
            LName[i].push_back(a);
        }
    }
    //将点名串插入AC自动机中
    for (int i=1;i<=m;i++) Insert(i);
    GetFail();//构建Fail指针
    for (int i=1;i<=n;i++) AhoCorasick(FName[i],i),AhoCorasick(LName[i],i);//分别把名字和姓氏放进去匹配
    for (int i=1;i<=m;i++) printf("%d\n",Ans1[NodeId[i]]);
    for (int i=1;i<=n;i++)
    {
        printf("%d",Ans2[i]);
        if (i!=n) printf(" ");
    }
    return 0;
}

vector<int> Input;

void Insert(int id)
{
    Input.clear();
    int L;scanf("%d",&L);
    for (int i=1;i<=L;i++){
        int a;scanf("%d",&a);
        Input.push_back(a);
    }
    int now=0;
    for (int i=0;i<L;i++)
    {
        if (T[now].Son[Input[i]]==0) T[now].Son[Input[i]]=++nodecnt;
        now=T[now].Son[Input[i]];
    }
    if (T[now].id==0) T[now].id=++idcnt;
    NodeId[id]=T[now].id;T[now].cnt++;
    return;
}

void GetFail()
{
    int h=0,t=0;
    for (iii=T[0].Son.begin();iii!=T[0].Son.end();iii++) Queue.push(iii->second);
    while (!Queue.empty())
    {

        int u=Queue.front();Queue.pop();
        if (T[u].Son.size()==0) continue;
        for (iii=T[u].Son.begin();iii!=T[u].Son.end();iii++)
        {
            int key=iii->first,id=iii->second;
            int now=T[u].fail;
            while ((now!=0)&&(T[now].Son[key]==0)) now=T[now].fail;
            if (T[now].Son[key]!=0) T[id].fail=T[now].Son[key];
            Queue.push(id);
        }
    }
    return;
}

void AhoCorasick(vector<int> V,int id)
{
    int L=V.size();
    int now=0;
    for (int i=0;i<L;i++)
    {
        if (T[now].Son[V[i]]!=0) now=T[now].Son[V[i]];
        else
        {
            while ((now!=0)&&(T[now].Son[V[i]]==0)) now=T[now].fail;
            if (T[now].Son[V[i]]!=0) now=T[now].Son[V[i]];
        }
        int p=now;
        while (p)
        {
            if (Hist[p]!=id)
            {
                Hist[p]=id;Ans2[id]+=T[p].cnt;Ans1[T[p].id]++;
            }
            p=T[p].fail;
        }
    }
    return;
}

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ2754/Luogu2336][SCOI2012]喵星球上的点名(AC自动机)


HNCJ OIer