BZOJ_4327_JSOI2012 玄武密码_AC自动机
2024-08-30 16:11:27
BZOJ_4327_JSOI2012 玄武密码_AC自动机
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
SNNSSNS
NNSS
NNN
WSEE
Sample Output
4
2
0
2
0
HINT
对于100%的数据,N<=10^7,M<=10^5,每一段文字的长度<=100。
按每段文字建立AC自动机。然后用母串在上面跑。
开个vis记录一下每个节点能否到达。
注意当x这个结点被经过时,x往上跳fail也能到达,所以需要每次暴力更新到第一个vis[x]=1的地方。
然后向下沿着trie树做DP即可,求出每个串的最大匹配长度。
代码:
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
inline char nc() {
static char buf[100000],*p1,*p2;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
int rd() {
int x=0; char s=nc();
while(s<'0'||s>'9') s=nc();
while(s>='0'&&s<='9') x=(x<<3)+(x<<1)+s-'0',s=nc();
return x;
}
#define N 10000050
int ch[N][4],fa[N],dep[N],fail[N],vis[N],f[N],cnt=1,end[100050],n,m,w[N],Q[N],l,r;
int _t(char s) {
if(s=='E') return 0;
if(s=='S') return 1;
if(s=='W') return 2;
if(s=='N') return 3;
return -1;
}
void insert(int idx) {
int p=1,q;
char s=nc(); while(_t(s)==-1) s=nc();
for(;(q=_t(s))!=-1;s=nc()) {
int &k=ch[p][q];
if(!k) k=++cnt;
dep[k]=dep[p]+1;
fa[k]=p;
p=k;
}
end[idx]=p;
}
void build_ac() {
l=0,r=0;
int i,p;
for(i=0;i<4;i++) ch[0][i]=1;
Q[r++]=1;
while(l<r) {
p=Q[l++];
for(i=0;i<4;i++) {
if(ch[p][i]) fail[ch[p][i]]=ch[fail[p]][i],Q[r++]=ch[p][i];
else ch[p][i]=ch[fail[p]][i];
}
}
}
int main() {
n=rd();
m=rd();
char s=nc(); while(_t(s)==-1) s=nc();
register int i;
for(i=1;i<=n;i++,s=nc()) {
w[i]=_t(s);
if(i==n) break;
}
for(i=1;i<=m;i++) {
insert(i);
}
build_ac();
int p=1;
for(i=1;i<=n;i++) {
p=ch[p][w[i]];
int q=p;
while(!vis[q]&&q) vis[q]=1,q=fail[q];
}
for(i=0;i<r;i++) {
p=Q[i];
f[p]=f[fa[p]];
if(vis[p]) f[p]=dep[p];
}
for(i=1;i<=m;i++) printf("%d\n",f[end[i]]);
}
最新文章
- js获得昨天前天明天时间以及setDate()
- SpringMVC从Controller跳转到另一个Controller
- 再见Unity3d的死循环
- IOS 网络浅析-(三 NSURLConnection代理)
- https 三次握手
- DataTable使用总结
- HDOJ2007平方和与立方和
- jQuery插件学习(一)
- PHP手册应注意
- .Net Service开发(一)
- RabbitMQ消息队列(二):”Hello, World“
- oracle数据库显示所有用户方法
- 解决Oracle登录时出现无法处理服务名问题
- 没有可用软件包 libgdiplus 解决方法
- 清理solaris /var/mail/下的邮件文件
- aop编程之后置通知,环绕通知和异常通知
- mysql联合主键自增、主键最大长度小记
- 安卓 dex 通用脱壳技术研究(三)
- MySQL的用户密码过期功能
- Package 设计3:数据源的提取和使用暂存