bzoj4327 玄武密码 [AC自动机]

in 题目 with 0 comment

Description

在美丽的玄武湖畔,鸡鸣寺边,鸡笼山前,有一块富饶而秀美的土地,人们唤作进香河。相传一日,一缕紫气从天而至,只一瞬间便消失在了进香河中。老人们说,这是玄武神灵将天书藏匿在此。
很多年后,人们终于在进香河地区发现了带有玄武密码的文字。更加神奇的是,这份带有玄武密码的文字,与玄武湖南岸台城的结构有微妙的关联。于是,漫长的破译工作开始了。
经过分析,我们可以用东南西北四个方向来描述台城城砖的摆放,不妨用一个长度为N的序列来描述,序列中的元素分别是‘E’,‘S’,‘W’,‘N’,代表了东南西北四向,我们称之为母串。而神秘的玄武密码是由四象的图案描述而成的M段文字。这里的四象,分别是东之青龙,西之白虎,南之朱雀,北之玄武,对东南西北四向相对应。
现在,考古工作者遇到了一个难题。对于每一段文字,其前缀在母串上的最大匹配长度是多少呢?


Input

第一行有两个整数,N和M,分别表示母串的长度和文字段的个数。
第二行是一个长度为N的字符串,所有字符都满足是E,S,W和N中的一个。
之后M行,每行有一个字符串,描述了一段带有玄武密码的文字。依然满足,所有字符都满足是E,S,W和N中的一个。


Output

输出有M行,对应M段文字。
每一行输出一个数,表示这一段文字的前缀与母串的最大匹配串长度。


Sample Input

7 3
SNNSSNS
NNSS
NNN
WSEE


Sample Output

4
2


HINT

对于100%的数据,N<=10^7,M<=10^5,每一段文字的长度<=100。


Solution

AC自动机模板题,对所有带匹配的字符串建一颗trie树,用类似KMP算法构造fail指针进行转移,用母串在trie树上匹配,详询


Code

#include<bits/stdc++.h>
#define maxn 10000010
//#define DEBUG
using namespace std;
int n,m,cnt=1;
int l[maxn],point[maxn],fa[maxn],fail[maxn];
int a[maxn][4];
bool pos[maxn];
char s[maxn],ch[maxn];

inline int read()
{
    char ch;
    int read=0,sign=1;
    do
        ch=getchar();
    while((ch<'0'||ch>'9')&& ch!='-');
    if(ch=='-') sign=-1,ch=getchar();
    while(ch>='0'&&ch<='9')
    {
        read=read*10+ch-'0';
        ch=getchar();
    }
    return sign*read;
}

inline int ID(char x)
{
    if(x=='N') return 0;
    if(x=='S') return 1;
    if(x=='W') return 2;
    if(x=='E') return 3;
    return -1;
}

inline void insert(int num)
{
    int now=1;
    l[num]=strlen(ch);
    for(int i=0;i<l[num];++i)
    {
        int u=ID(ch[i]);
//      cout<<"u="<<u<<endl;
        if(a[now][u]) now=a[now][u];
        else
        {
            a[now][u]=++cnt;
            fa[a[now][u]]=now;
            now=a[now][u];
        }
    }
    point[num]=now;
}

void getfail()
{
    queue<int> q;
    q.push(1);
    fail[1]=0;
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        for(int i=0;i<4;++i)
        {
            int k=fail[u];
            while(!a[k][i]) k=fail[k];
            if(a[u][i])
            {
                fail[a[u][i]]=a[k][i];
                q.push(a[u][i]);
            }
            else a[u][i]=a[k][i];
        }
    }
}

void pre()
{
    int now=1;
    for(int i=0;i<n;++i)
    {
        int u=ID(s[i]);
        now=a[now][u];
        for(int j=now;j;j=fail[j])
            if(pos[j]) break;
            else pos[j]=1;
    }
}

int getans(int x)
{
    int ans=l[x];
    for(int i=point[x];i;i=fa[i])
    {
        if(pos[i]) return ans;
        ans--;
    }
    return 0;
}

int main()
{
    n=read(),m=read();
    scanf("%s",s);
    for(int i=1;i<=m;++i)
    {
        scanf("%s",ch);
        insert(i);
    }
    for(int i=0;i<4;++i) a[0][i]=1;
    getfail();
#ifdef DEBUG
    for(int i=1;i<=m;++i) cerr<<l[i]<<" ";
    cerr<<endl;
    for(int i=0;i<=10;++i){
        for(int j=0;j<4;++j)
            cerr<<a[i][j]<<" ";
        cerr<<endl;}
#endif
    pre();
    for(int i=1;i<=m;++i) printf("%d\n",getans(i));
    return 0;
}

扫描二维码,在手机上阅读!
Responses