P5231 [JSOI2012]玄武密码

链接

分析:

  首先对所有询问串建立AC自动机,然后扫描一遍母串,在AC自动机上走,没走到一个点,标记这个点走过了,并且它的fail树上的祖先节点也可以访问到(即可以匹配到主串),于是沿着fail树打标记,当到一个已经打过标记的点的时候,退出。这样保证每个点只会被打标机一次。询问时,在AC自动机上倒着往前走,走到第一个打过标记的点的时候,从AC自动机的根节点到这个点的距离就是答案。复杂度$O(N+100M)$。

代码:

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<cmath>
#include<cctype>
#include<set>
#include<queue>
#include<vector>
#include<map>
using namespace std;
typedef long long LL; inline int read() {
int x=,f=;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-;
for(;isdigit(ch);ch=getchar())x=x*+ch-'';return x*f;
} const int SZ = , N = ;
int id[], len[N], pos[N], ch[SZ][], fa[SZ], q[SZ], fail[SZ], Index;
bool vis[SZ];
char s[SZ], t[]; void Insert(char *s,int k) {
int u = ;
for (int i = ; i <= len[k]; ++i) {
int c = id[(int)s[i]];
if (!ch[u][c]) ch[u][c] = ++Index, fa[Index] = u;
u = ch[u][c];
}
pos[k] = u;
}
void bfs() {
int L = , R = ;
for (int i = ; i <= ; ++i) if (ch[][i]) q[++R] = ch[][i];
while (L <= R) {
int u = q[L ++];
for (int c = ; c <= ; ++c) {
int v = ch[u][c];
if (!v) ch[u][c] = ch[fail[u]][c];
else fail[v] = ch[fail[u]][c], q[++R] = v;
}
}
}
int Calc(int x) {
int ans = len[x];
for (int i = pos[x]; i; i = fa[i], ans --)
if (vis[i]) return ans;
}
int main() {
int n = read(), m = read();
id['E'] = , id['S'] = , id['W'] = , id['N'] = ;
scanf("%s", s + );
for (int i = ; i <= m; ++i) {
scanf("%s", t + );
len[i] = strlen(t + );
Insert(t, i);
}
bfs();
int u = , v;
for (int i = ; i <= n; ++i) {
int c = id[(int)s[i]];
u = ch[u][c];
v = u;
while (v && !vis[v]) vis[v] = , v = fail[v];
}
for (int i = ; i <= m; ++i)
printf("%d\n", Calc(i));
return ;
}
04-25 19:14