|
|
#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 n, m; // 母串的长度n,m个模式串
|
|
|
bool st[M]; // st[i]:标识i结点是不是母串可以到达的位置
|
|
|
|
|
|
//这种字符向数字进行映射的问题，最好的办法就是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];
|
|
|
}
|
|
|
}
|
|
|
|
|
|
//构建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 (st[j]) break; // 这句加上，性能会好一点; 不加也一样能AC。
|
|
|
st[j] = true; // 标识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 (st[p]) res = j + 1; //如果标识过此位置，那么结果更新为最长前缀的长度j+1
|
|
|
}
|
|
|
printf("%d\n", res); //输出最长长缀长度
|
|
|
}
|
|
|
return 0;
|
|
|
} |
