【题解】bzoj 4327 JSOI2012 玄武密码

原题传送门

我们先对所有询问串建立AC自动机（今天洛咕上有人分不清AC自动机和自动AC机）

然后将母串在AC自动机上跑，每走到一个点x，从x点出发沿着fail指针所能到的所有前缀都是匹配成功的，暴力向上走，碰到走过的就break（剩下的肯定都走过），这样每个点最多被标记1次

最后再把每个询问串走一遍统计答案

时间复杂度为(O(N+100M))

#include <bits/stdc++.h>
#define N 10000005
#define M 105
#define K 100005
using namespace std;
inline void write(register int x)
{
    if(!x)putchar('0');if(x<0)x=-x,putchar('-');
    static int sta[20];register int tot=0;
    while(x)sta[tot++]=x%10,x/=10;
    while(tot)putchar(sta[--tot]+48);
}
int tx[50],n,m; 
struct Aho_corasick_Automaton{
	int c[N][5],end[K],fail[N],cnt,l[K],pre[N],flag[N];
	queue<int> q;
	inline void ins(register char *s,register int t)
	{
		int len=strlen(s),now=0;
		l[t]=len;
		for(register int i=0;i<len;++i)
		{
			int v=tx[s[i]-'A'];
			if(!c[now][v])
				c[now][v]=++cnt,pre[cnt]=now;
			now=c[now][v];
		}
		end[t]=now;
	}
	inline void build()
	{
		for(register int i=0;i<4;++i)
			if(c[0][i])
				fail[c[0][i]]=0,q.push(c[0][i]);
		while(!q.empty())
		{
			int u=q.front();
			q.pop();
			for(register int i=0;i<4;++i)
				if(c[u][i])
					fail[c[u][i]]=c[fail[u]][i],q.push(c[u][i]);
				else
					c[u][i]=c[fail[u]][i]; 
		}
	}
	inline void find(register char *s)
	{
		int len=strlen(s),now=0;
		for(register int i=0;i<len;++i)
		{
			int v=tx[s[i]-'A'];
			now=c[now][v];
			int k=now;
			while(k>1)
			{
				if(flag[k])
					break;
				flag[k]=1;
				k=fail[k];
			}
		}
	}
	inline int solve(register int t)
	{
		int now=end[t];
		for(register int i=l[t];i;--i)
		{
			if(flag[now])
				return i;
			now=pre[now];
		}
		return 0;
	}
}ac;
char s[N],st[M];
int main()
{
	tx['E'-'A']=0,tx['S'-'A']=1,tx['W'-'A']=2,tx['N'-'A']=3;
	scanf("%d%d",&n,&m);
	scanf("%s",s);
	for(register int i=1;i<=m;++i)
	{
		scanf("%s",st);
		ac.ins(st,i);
	}
	ac.build();
	ac.find(s);
	for(register int i=1;i<=m;++i)
		write(ac.solve(i)),puts("");
	return 0;
 }