网站最近不收录,wordpress百度网盘,宜城网站开发,wordpress卡核销Description 在美丽的玄武湖畔#xff0c;鸡鸣寺边#xff0c;鸡笼山前#xff0c;有一块富饶而秀美的土地#xff0c;人们唤作进香河。相传一日#xff0c;一缕紫气从天而至#xff0c;只一瞬间便消失在了进香河中。老人们说#xff0c;这是玄武神灵将天书藏匿在此。 很…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%的数据N10^7M10^5每一段文字的长度100。 Solution $SAM$板子…… Code 1 #includeiostream2 #includecstring3 #includecstdio4 #define N (20000007)5 using namespace std;6 7 int n,m,v[109];8 char s[N];9
10 struct SAM
11 {
12 int p,q,np,nq,last,cnt;
13 int fa[N],son[N][4],step[N];
14 SAM() {lastcnt1;}
15
16 void Insert(int x)
17 {
18 plast; nplastcnt; step[np]step[p]1;
19 while (p !son[p][x]) son[p][x]np, pfa[p];
20 if (!p) fa[np]1;
21 else
22 {
23 qson[p][x];
24 if (step[q]step[p]1) fa[np]q;
25 else
26 {
27 nqcnt; step[nq]step[p]1;
28 memcpy(son[nq],son[q],sizeof(son[q]));
29 fa[nq]fa[q]; fa[q]fa[np]nq;
30 while (son[p][x]q) son[p][x]nq, pfa[p];
31 }
32 }
33 }
34 int Query(char s[])
35 {
36 int lenstrlen(s),ans0,x1;
37 for (int i0; ilen; i)
38 {
39 if (!son[x][v[s[i]]]) return ans;
40 ans; xson[x][v[s[i]]];
41 }
42 return ans;
43 }
44 }SAM;
45
46 int main()
47 {
48 v[E]0; v[S]1; v[W]2; v[N]3;
49 scanf(%d%d%s,n,m,s);
50 for (int i0; in; i) SAM.Insert(v[s[i]]);
51 for (int i1; im; i) scanf(%s,s), printf(%d\n,SAM.Query(s));
52 } 转载于:https://www.cnblogs.com/refun/p/10520725.html
