题目是要求多个串在母串上的最长匹配长度。
考虑 \(\text{AC}\) 自动机，我们建出 \(\text{Trie}\) 图然后用母串来在上面跑。
每一个能匹配的位置，它 \(\text{fail}\) 的位置也一定可以匹配，我们就跳 \(\text{fail}\) 把经过的节点的值赋为 \(1\) ，表示这个位置可以匹配。
然后我们每一个模式串，找到ta在 \(\text{Trie}\) 树上最深的可以匹配的节点来计算答案即可。
参考代码：
#include <cstring>#include <cstdio>#define rg register#define file(x) freopen(x".in", "r", stdin), freopen(x".out", "w", stdout)template < class T > inline void read(T& s) { s = 0; int f = 0; char c = getchar(); while ('0' > c || c > '9') f |= c == '-', c = getchar(); while ('0' <= c && c <= '9') s = s * 10 + c - 48, c = getchar(); s = f ? -s : s;}const int _ = 1e7 + 5, __ = 1e5 + 5;char a[_], s[_][102]; int n, m;int tot, ch[4][_], fail[_], vis[_];inline int cg(char c) { if (c == 'E') return 0; if (c == 'S') return 1; if (c == 'W') return 2; if (c == 'N') return 3; }inline void insert(int x) { int u = 0, len = strlen(s[x] + 1); for (rg int i = 1; i <= len; ++i) { int c = cg(s[x][i]); if (!ch[c][u]) ch[c][u] = ++tot; u = ch[c][u]; }}inline void build() { static int hd, tl, Q[_]; hd = tl = 0; for (rg int c = 0; c < 4; ++c) if (ch[c][0]) Q[++tl] = ch[c][0]; while (hd < tl) { int u = Q[++hd]; for (rg int c = 0; c < 4; ++c) { if (!ch[c][u]) ch[c][u] = ch[c][fail[u]]; else fail[ch[c][u]] = ch[c][fail[u]], Q[++tl] = ch[c][u]; } }}inline void query() { int u = 0, len = strlen(a + 1); for (rg int i = 1; i <= len; ++i) { u = ch[cg(a[i])][u]; for (rg int v = u; v; v = fail[v]) if (!vis[v]) vis[v] = 1; else break ; }}inline int calc(int x) { int u = 0, len = strlen(s[x] + 1), res = 0; for (rg int i = 1; i <= len; ++i) { u = ch[cg(s[x][i])][u]; if (vis[u]) res = i; } return res;}int main() {#ifndef ONLINE_JUDGE file("cpp");#endif read(n), read(m), scanf("%s", a + 1); for (rg int i = 1; i <= m; ++i) scanf("%s", s[i] + 1), insert(i); build(); query(); for (rg int i = 1; i <= m; ++i) printf("%d\n", calc(i)); return 0;}
