\(P5231\) [\(JSOI2012\)]玄武密码
一、题目背景
在美丽的玄武湖畔，鸡鸣寺边，鸡笼山前，有一块富饶而秀美的土地，人们唤作进香河。相传一日，一缕紫气从天而至，只一瞬间便消失在了进香河中。老人们说，这是玄武神灵将天书藏匿在此。
很多年后，人们终于在进香河地区发现了带有玄武密码的文字。更加神奇的是，这份带有玄武密码的文字，与玄武湖南岸台城的结构有微妙的关联。于是，漫长的破译工作开始了。
题目描述
经过分析，我们可以用东南西北四个方向来描述台城城砖的摆放，不妨用一个长度为 \(n\) 的序列 \(s\) 来描述，序列中的元素分别是 \(E，S，W，N\)，代表了东南西北四向，我们称之为母串。而神秘的玄武密码是由四象的图案描述而成的 \(m\) 段文字。这里的四象，分别是东之青龙，西之白虎，南之朱雀，北之玄武，对东南西北四向相对应。
现在，考古工作者遇到了一个难题。对于每一段文字 \(t\)，求出其最长的前缀 \(p\)，满足 \(p\) 是 \(s\) 的子串。
二、题目解析
这题虽说是板子，但也不能只用板子，是一道比较不错的\(AC\)自动机题目。首先发现多模式串，二话不说上\(AC\)自动机，但是发现只有\(E\)、\(S\)、\(W\)、\(N\)这四个字母，所以可以优化一下建立起从\(E\)、\(S\)、\(W\)、\(N\)到\(a\)、\(b\)、\(c\)、\(d\)的映射就好了。
要查询每个模式串的前缀与母串的最大匹配长度，那我们就在\(Trie\)树上标记母串所有的可以匹配到的位置，然后对于每一个模式串，我们就从它的\(Trie\)树上进行检索，当发现第一个没有被母串匹配到的结点时，当前长度就是最大的匹配长度。
另外还有一个 小小的优化，如果说对于一个节点它已经被标记过了，那么它的\(ne\)链上的所有点一定也被标记了，所以这时就可以直接\(break\)。
三、实现代码
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
const int N = 1e5 + 10; //模式串的个数最多是1e5个
const int M = 1e7 + 10; //母串的最长长度不会超过1e7
char s[N][110]; // 模式串的长度最长不超过100
char T[M]; // 母串
int tr[M][4], idx; // AC自动机需要的Trie树，idx:点的索引号
int id[N]; // 每个模式串，最终的终点是Trie树中的哪个节点号
int n, m; // 母串的长度n,m个模式串
int cnt[M]; // ???
//这种字符向数字进行映射的问题，最好的办法就是if,其它的什么Hash化都是渣渣~
int get(char x) {
if (x == 'N') return 0;
if (x == 'E') return 1;
if (x == 'S') return 2;
if (x == 'W') return 3;
}
void insert(char *s, int x) {
int p = 0;
for (int i = 0; s[i]; i++) {
int t = get(s[i]); //这里有映射关系与标准模板是有差别的 int t = s[i] - 'a';
if (!tr[p][t]) tr[p][t] = ++idx;
p = tr[p][t];
}
//记录每个模式串的终点号码，为什么要记录每个模式串的终点号呢？
id[x] = p; //记录x号模式串，在trie树中的终点是p
}
//构建AC自动机，也就是在维护失配指针。这里与标准模板一模一样
int q[M], ne[M]; //这里使用M，是因为模式串个数是1e5个，每个长度是100，所以总共的基于模式串创建Trie树，节点总个数是1e5*100=1e7，恰好与M一样而已
void bfs() {
int hh = 0, tt = -1;
for (int i = 0; i < 4; i++)
if (tr[0][i]) q[++tt] = tr[0][i];
while (hh <= tt) {
int p = q[hh++];
for (int i = 0; i < 4; i++) {
int t = tr[p][i];
if (!t)
tr[p][i] = tr[ne[p]][i];
else {
ne[t] = tr[ne[p]][i];
q[++tt] = t;
}
}
}
}
//在通过模式串构建的Trie图上，跑一遍母串，目的是标识母串走了哪些点，这些点，就是每个模式串的最长前缀所到达的位置
//在query操作中，将对于母串到达的每个位置进行标记
void query(char *s) {
int p = 0; //从根开始,根节点在模板中设置为0
for (int i = 0; s[i]; i++) { //枚举母串的每个字符，看看母串都可以到达哪些 Trie树上的节点
p = tr[p][get(s[i])]; //从根开始，通过输入的字符，映射到相应的数字0~3,找到它可以到达的点
for (int j = p; j; j = ne[j]) { // p点可以到达，那么一旦下一个位置失配时，ne[p]也可以到达的，因为它们有共同的前缀？
//另外还有一个小小的优化，如果说对于一个节点它已经被标记过了，那么它的$ne$链上的所有点一定也被标记了，所以这时就可以直接$break$。
if (cnt[j]) break; // 这句加上，性能会好一点; 不加也一样能AC。
cnt[j] = 1; // 标识j点是母串可以到达的点
}
}
}
int main() {
//加快读入
ios::sync_with_stdio(false), cin.tie(0);
//第一行有两个整数，分别表示母串的长度 n 和文字段的个数 m
cin >> n >> m;
//第二行有一个长度为 n 的字符串，表示母串 T
//如果是输入一串字符串并保存到字符数组中，系统会自动在后面补\0，无需自己输入。
//也就是不需要知道到底这个字符串的真实长度，n无用
cin >> T;
// m个模式串
for (int i = 1; i <= m; i++) {
cin >> s[i];
/*
使用s[]数组记录都录入了哪些模式串，这里的s是一个二维数组，
第一维表示录入的顺序号，第二维是真正的字符串内容，最长长度不超过100
*/
insert(s[i], i);
}
//构建AC自动机
bfs();
//上母串，标记母串所有可以匹配到的位置
query(T);
//对于每一个模式串，我们就从它的$Trie$树上进行检索，当发现第一个没有被母串匹配到的结点时，当前长度就是最大的匹配长度
for (int i = 1; i <= m; i++) { //枚举每个模式串
int res = 0, p = 0;
for (int j = 0; s[i][j]; j++) { //枚举每个模式串的所有前缀
p = tr[p][get(s[i][j])]; //沿着Trie前进
if (cnt[p]) res = j + 1; //如果标识过此位置，那么结果更新为最长前缀的长度j+1
}
printf("%d\n", res); //输出最长长缀长度
}
return 0;
}