【BZOJ4327】[JSOI2012] 玄武密码（AC自动机的小应用）

点此看题面

大致题意： 给你一个长度为\(len\)的文本串和\(n\)个模式串，让你求出每一个模式串的前缀与文本串的最大匹配串长度（其中模式串和文本串都只由字符'E','S','W','N'组成）。

\(AC\)自动机

这是一道\(AC\)自动机的简单运用题。

题解

对于每一个模式串，我们可以记录它的每一个前缀在\(Trie\)上所对应的节点的位置。

在用\(AC\)自动机时，对每一个访问过的节点打个标记，如果遇到已经访问过的节点就\(break\)（因为接下来的节点肯定在第一次访问当前节点时被访问过，不需要重复访问）。

最后输出答案时，对于每一个模式串，只要从后往前枚举它的每一个前缀，一旦遇到一个被访问过的，就输出并结束枚举。

代码

#include<bits/stdc++.h>

#define max(x,y) ((x)>(y)?(x):(y))

#define min(x,y) ((x)<(y)?(x):(y))

#define LL long long

#define ull unsigned long long

#define swap(x,y) (x^=y,y^=x,x^=y)

#define tc() (A==B&&(B=(A=ff)+fread(ff,1,100000,stdin),A==B)?EOF:*A++)

#define pc(ch) (pp_<100000?pp[pp_++]=(ch):(fwrite(pp,1,100000,stdout),pp[(pp_=0)++]=(ch)))

#define N 100000

int pp_=0;char ff[100000],*A=ff,*B=ff,pp[100000];

using namespace std;

int n,len,ee=0,rt=1,tot=1,lens[N+5],ans[N+5][100];

string st;

struct Trie

{

    int Son[4],Next,Vis;

}node[100*N+5];

queue<int> q;

inline void read(int &x)

{

    x=0;static char ch;

    while(!isdigit(ch=tc()));

    while(x=(x<<3)+(x<<1)+ch-48,isdigit(ch=tc()));

}

inline void write(int x)

{

    if(x>9) write(x/10);

    pc(x%10+'0');

}

inline void read_string(string &x)

{

    x="";static char ch;

    while(isspace(ch=tc()));

    while(x+=ch,!isspace(ch=tc())) if(!(~ch)) return;

}

inline int GetPos(char x)//由于只有4个字符，我们可以将其压缩

{

    return x=='E'?0:(x=='W'?1:(x=='N'?2:3));

}

inline void Insert(int pos,string st)//将编号为pos的模式串st插入字典树中

{

    register int i,nxt,x=rt,len=lens[pos];

    for(i=0;i<len;++i)

    {

        if(!node[x].Son[nxt=GetPos(st[i])]) node[x].Son[nxt]=++tot;

        ans[pos][i]=x=node[x].Son[nxt];//记录当前模式串每一个前缀最后到达的节点

    }

}

inline void GetNext()//求出失配指针

{

    register int i,k;q.push(rt);

    while(!q.empty())

    {

        k=q.front(),q.pop();

        for(i=0;i<4;++i)

        {

            if(k^rt)

            {

                if(!node[k].Son[i]) node[k].Son[i]=node[node[k].Next].Son[i];

                else node[node[k].Son[i]].Next=node[node[k].Next].Son[i],q.push(node[k].Son[i]);

            }

            else

            {

                if(!node[k].Son[i]) node[k].Son[i]=rt;

                else node[node[k].Son[i]].Next=rt,q.push(node[k].Son[i]);

            }

        }

    }

}

inline void AC_Automation()//AC自动机的核心代码

{

    register int i,j,x=rt;

    for(GetNext(),i=0;i<len;++i)

    {

        if(!(x=node[x].Son[GetPos(st[i])])) {x=rt;continue;}

        int p=x;

        while(p)

        {

            if(!node[p].Vis) node[p].Vis=1;//如果当前节点未访问过，就标记已访问

            else break;//如果已访问过，就break

            p=node[p].Next;

        }

    }

}

int main()

{

    register int i,j;register string s;

    for(read(len),read(n),read_string(st),tot=i=1;i<=n;++i) read_string(s),lens[i]=s.length(),Insert(i,s);

    for(AC_Automation(),i=1;i<=n;++i)

    {

        for(j=lens[i];j>=0;--j)//从后往前枚举当前模式串的每一个前缀

        {

            if(!j) pc('0'),pc('\n');

            else if(node[ans[i][j-1]].Vis) {write(j),pc('\n');break;}//如果当前节点被访问过，就输出答案并枚举下一个模式串

        }

    }

    return fwrite(pp,1,pp_,stdout),0;

}

巴特西

【BZOJ4327】[JSOI2012] 玄武密码（AC自动机的小应用）

\(AC\)自动机

题解

代码

最新文章

热门文章