BZOJ4327: JSOI2012 玄武密码【AC自动机】

4327: JSOI2012 玄武密码

【题目描述】

传送门

【题解】

拿大串在AC自动机上匹配,如果小串第i位被匹配了,那么匹配前缀就是i。
枚举小串匹配前缀长度,然后判断是否匹配过(可以在大串匹配是预处理出来)。

【代码如下】

#include<cstdio>
#include<cstring>
using namespace std;
const int MAXP=1e7+5,MAXN=1e5+5,MAXL=105;
int n,m,L[MAXN];bool F[MAXP];
char s[MAXP],ch[105];
struct AC{
    int hd,tl,que[MAXN*MAXL],fa[MAXN*MAXL],Son[MAXN*MAXL][4],pre[MAXN*MAXL],W[MAXN],cnt;
    int get(char ch){if(ch=='W') return 0;else if(ch=='E') return 1;else if(ch=='S') return 2;else if(ch=='N') return 3;}
    void Insert(char *s,int Len,int t){
        int Now=0;
        for(int i=0,w;i<Len;i++){
            if(!Son[Now][w=get(s[i])]) fa[Son[Now][w]=++cnt]=Now;
            Now=Son[Now][w];
        }
        W[t]=Now;
    }
    void Build(){
        hd=tl=0;
        for(int i=0;i<4;i++)
        if(Son[0][i]) pre[que[++tl]=Son[0][i]]=0;else Son[0][i]=0;
        while(hd^tl){
            int x=que[++hd];
            for(int i=0;i<4;i++)
            if(Son[x][i]){
                int Now=pre[x];
                while(Now&&!Son[Now][i]) Now=pre[Now];
                pre[que[++tl]=Son[x][i]]=Son[Now][i];
            }else Son[x][i]=Son[pre[x]][i];
        }
    }
    void Fnd(char *s,int Len){
        int Now=0;
        for(int i=0,w;i<Len;i++){
            while(!Son[Now][w=get(s[i])]&&Now) Now=pre[Now];
            if(Son[Now][w]){
                int p=(Now=Son[Now][w]);
                while(p&&!F[p]) F[p]=1,p=pre[p];
            }
        }
    }
    int Ask(int t,int Len){
        for(int i=Len,Now=W[t];i;i--,Now=fa[Now])
        if(F[Now]) return i;
        return 0;
    }
}Tre;
int main(){
    #ifndef ONLINE_JUDGE
    freopen("prob.in","r",stdin);
    freopen("prob.out","w",stdout);
    #endif
    scanf("%d%d%s",&n,&m,s);
    for(int i=1;i<=m;i++) scanf("%s",ch),Tre.Insert(ch,L[i]=strlen(ch),i);
    Tre.Build();Tre.Fnd(s,n);
    for(int i=1;i<=m;i++) printf("%d\n",Tre.Ask(i,L[i]));
    return 0;
}

发表评论

开始在上面输入您的搜索词,然后按回车进行搜索。按ESC取消。

返回顶部