题目思路没话讲；主要是做题时候的细节和经验
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。
题目分析
题目的做法很显然：标记一下哪些节点被匹配过，之后再dfs找被匹配过的最大深度。
这里记录一下做题经验：
- 字符集能压缩的尽量压缩（和离散化一个道理），trie毕竟还有|S|的常数在这里。
- 查询跳匹配的时候for (int v=u; v&&!vis[v]; v=nxt[v])的!vis[v]这个优化非常重要
以上。
1 #include<bits/stdc++.h> 2 const int maxNode = 10000035; 3 const int maxn = 10000035; 4 ?5 char s[maxn],t[103]; 6 int n,m,c[100035],l[100035],cnt; 7 struct ACAutomaton 8 { 9 ????bool vis[maxNode];10 ????std::queue<int> q;11 ????int nxt[maxNode],f[maxNode][5],fa[maxNode],tot;12 ????13 ????inline int get(char ch)14 ????{15 ????????if(ch==‘W‘) return 0;16 ????????if(ch==‘E‘) return 1;17 ????????if(ch==‘S‘) return 2;18 ????????return 3;19 ????}20 ????void insert(char *s)21 ????{22 ????????int u = 1, lens = strlen(s);23 ????????for (int i=0; i<lens; i++)24 ????????{25 ????????????int c = get(s[i]);26 ????????????if (!f[u][c]) f[u][c] = ++tot, fa[f[u][c]] = u;27 ????????????u = f[u][c];28 ????????}29 ????????c[++cnt] = u;30 ????}31 ????void build()32 ????{33 ????????for (int i=0; i<4; i++) f[0][i] = 1;34 ????????q.push(1);35 ????????while (q.size())36 ????????{37 ????????????int tt = q.front();38 ????????????q.pop();39 ????????????for (int i=0; i<4; i++)40 ????????????????if (f[tt][i])41 ????????????????????nxt[f[tt][i]] = f[nxt[tt]][i], q.push(f[tt][i]);42 ????????????????else f[tt][i] = f[nxt[tt]][i];43 ????????}44 ????}45 ????int query(int s, int t)46 ????{47 ????????for (; s; s=fa[s], t--)48 ????????????if (vis[s]) return t;49 ????????return 0;50 ????}51 ????void match(char *s)52 ????{53 ????????int u = 1, lens = strlen(s);54 ????????for (int i=0; i<lens; i++)55 ????????{56 ????????????int c = get(s[i]);57 ????????????u = f[u][c];58 ????????????for (int v=u; v&&!vis[v]; v=nxt[v]) vis[v] = 1;59 ????????}60 ????}61 }f;62 63 int main()64 {65 ????scanf("%d%d%s",&n,&m,s);66 ????f.tot = 1;67 ????for (int i=1; i<=m; i++)68 ????{69 ????????scanf("%s",t);70 ????????f.insert(t);71 ????????l[i] = strlen(t);72 ????}73 ????f.build(), f.match(s);74 ????for (int i=1; i<=m; i++)75 ????????printf("%d\n",f.query(c[i], l[i]));76 ????return 0;77 }END
【AC自动机】bzoj4327: JSOI2012 玄武密码
原文地址：https://www.cnblogs.com/antiquality/p/9594916.html