[BZOJ4327]JSOI2012 玄武密码 AC自动机


原题链接
给定母串和一堆模式串,求每个模式串的最长前缀匹配.
建立AC自动机,将母串扔进去跑,然后分别在原树上和fail树上收集一下访问标记即可.
10^7的串长看着很吓人,实际上注意空间即可.

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 10002333
#define M 102333
using namespace std;
int n,m;
char s[N],t[M];
inline int id(char c)
{
    switch(c)
    {
        case 'E':return 0;
        case 'S':return 1;
        case 'W':return 2;
        case 'N':return 3;
    }
}
int head[N],to[N],nxt[N],cnt;
inline void add(int x,int y)
{
    to[++cnt]=y;
    nxt[cnt]=head[x];
    head[x]=cnt;
}
int ch[N][4],fail[N],deep[N],fa[N],node[M],tot=1;
char c[N];
bool v[N];
inline int insert(char *str)
{
    int x=1,len=strlen(str),i,tmp;
    for(i=0;i<len;++i)
    {
        tmp=id(str[i]);
        if(!ch[x][tmp])ch[x][tmp]=++tot;
        c[ch[x][tmp]]=str[i],x=ch[x][tmp];
    }
    return x;
}
int q[N],l=1,r;
void build_fail()
{
    int x,i;
    for(i=0;i<4;++i)
    {
        if(!ch[1][i])ch[1][i]=1;
        else deep[ch[1][i]]=1,fa[ch[1][i]]=1,add(1,ch[1][i]),fail[ch[1][i]]=1,q[++r]=ch[1][i];
    }
    while(l<=r)
    {
        x=q[l++];
        for(i=0;i<4;++i)
        {
            if(!ch[x][i])ch[x][i]=ch[fail[x]][i];
            else deep[ch[x][i]]=deep[x]+1,fa[ch[x][i]]=x,add(ch[fail[x]][i],ch[x][i]),fail[ch[x][i]]=ch[fail[x]][i],q[++r]=ch[x][i];
        }
    }
}
void dfs1(int x)
{
    for(int i=0;i<4;++i)if(deep[ch[x][i]]==deep[x]+1)
    {
        dfs1(ch[x][i]);
        v[x]|=v[ch[x][i]];
    }
}
void dfs2(int x)
{
    for(int i=head[x];i;i=nxt[i])dfs2(to[i]),v[x]|=v[to[i]];
}
int main()
{
    cin>>n>>m;
    scanf("%s",s);
    for(int i=1;i<=m;++i)
    {
        scanf("%s",t);
        node[i]=insert(t);
    }
    build_fail();
    int x=1;
    for(int i=0;i<n;++i)
    {
        x=ch[x][id(s[i])];
        v[x]=1;
    }
    dfs1(1);dfs2(1);
    for(int x,i=1;i<=m;++i)
    {
        for(x=node[i];!v[x];x=fa[x]);
        printf("%d\n",deep[x]);
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注