4327: JSOI2012 玄武密码
Time Limit: 10 Sec Memory Limit: 512 MB
Submit: 43 Solved: 20
[Submit][Status][Discuss]
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
Sample Output
4
2
0
HINT
对于100%的数据,N<=10^7,M<=10^5,每一段文字的长度<=100。
用AC自动机。
首先,我们把所有的匹配串放进自动机,我们可以计算出每个点的字符串是否出现在模式串中。这只需要把模式串在自动机上走一趟,每走到一个点就一直访问后缀节点直到到达了根节点,访问过的点都标记一下。然后每个点只会被访问一次。这样我们就处理完了所有点是否出现在模式串中。对于每个字符串计算答案时,从最后一个点访问起,每次走到它的父亲,一旦走到的点被标记过,就输出当前的长度,退出。
我也感觉非常精妙。。
代码:
#include<cstdio> #include<cstring> using namespace std; int n,m,len,now,num,p1,p2,u,v; int q[10000010],hz[10000010],fa[10000010],id[10000010],l[10000010],flag[10000010],trie[10000010][4]; char str[10000010],s[110]; int ord(char ch){if (ch=='E') return 0;if (ch=='S') return 1;if (ch=='W') return 2;return 3;} void bfs() { p2=1; while (p1<p2) { p1++; u=q[p1]; for (int i=0;i<4;i++) if (trie[u][i]) { v=trie[u][i]; if (!u) hz[v]=0;else hz[v]=trie[hz[u]][i]; q[++p2]=v; }else trie[u][i]=trie[hz[u]][i]; } } int main() { scanf("%d%d",&n,&m); scanf("%s",str); for (int i=1;i<=m;i++) { scanf("%s",s); len=strlen(s); now=0; for (int j=0;j<len;j++) if (trie[now][ord(s[j])]) now=trie[now][ord(s[j])];else { num++; trie[now][ord(s[j])]=num; fa[num]=now; now=num; } id[i]=now;l[i]=len; } bfs(); u=0; for (int i=0;i<n;i++) { u=trie[u][ord(str[i])]; for (v=u;v;v=hz[v]) if (flag[v]) break;else flag[v]=1; } for (int i=1;i<=m;i++) { u=id[i]; for (;l[i];l[i]--,u=fa[u]) if (flag[u])break; printf("%d\n",l[i]); } }