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。

Solution

$SAM$板子……

Code

1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 #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() {last=cnt=1;} 15 16 void Insert(int x) 17 { 18 p=last; np=last=++cnt; step[np]=step[p]+1; 19 while (p && !son[p][x]) son[p][x]=np, p=fa[p]; 20 if (!p) fa[np]=1; 21 else 22 { 23 q=son[p][x]; 24 if (step[q]==step[p]+1) fa[np]=q; 25 else 26 { 27 nq=++cnt; 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, p=fa[p]; 31 } 32 } 33 } 34 int Query(char s[]) 35 { 36 int len=strlen(s),ans=0,x=1; 37 for (int i=0; i<len; ++i) 38 { 39 if (!son[x][v[s[i]]]) return ans; 40 ++ans; x=son[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 i=0; i<n; ++i) SAM.Insert(v[s[i]]); 51 for (int i=1; i<=m; ++i) scanf("%s",s), printf("%d\n",SAM.Query(s)); 52 }

轉載于:https://www.cnblogs.com/refun/p/10520725.html

總結

以上是生活随笔為你收集整理的BZOJ4327:[JSOI2012]玄武密码(SAM)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。