对于100%的数据，N<=10^7，M<=10^5，每一段文字的长度<=100。
应上传者要求，此题不公开，如有异议，请提出.
每到一个节点，它跳fail指针一直调到根所经过的节点一定是可以匹配的节点。
所以对于询问串建trie树，记录每个串的结尾节点和每个节点的父亲节点。
然后AC自动机匹配的时候每到一个节点，就跳fail指针并打上标记，遇到打标记的点就退出，保证每个点只访问一遍。
然后处理询问就从串的结尾向上走遇到被标记的节点就退出。
#include <iostream> #include <cstdio> #include <queue> #include <cstring> #include <algorithm> using namespace std; #define reg register inline int read() { int res=0;char ch=getchar(); while(!isdigit(ch)) ch=getchar(); while(isdigit(ch))res=(res<<3)+(res<<1)+(ch^48),ch=getchar(); return res; } #define N 10000005 int n, m; int nxt[N][5], fail[N], cnt; int mark[N]; char str[N], stt[100005][105], len[100005]; int end[100005], fa[N]; inline int id(char c) { if (c == ‘N‘) return 1; if (c == ‘S‘) return 3; if (c == ‘W‘) return 2; return 4; } inline void ins(int i) { len[i] = strlen(stt[i] + 1); int p = 1; int now = 0; while(p <= len[i]) { if (!nxt[now][id(stt[i][p])]) nxt[now][id(stt[i][p])] = ++cnt, fa[cnt] = now; now = nxt[now][id(stt[i][p])]; p++; } end[i] = now; } inline void AC_Match() { queue <int> q; fail[0] = -1; for (reg int i = 1 ; i <= 4 ; i ++) if (nxt[0][i]) q.push(nxt[0][i]), fail[nxt[0][i]] = 0; while(!q.empty()) { int x = q.front(); q.pop(); for (reg int i = 1 ; i <= 4 ; i ++) { if (nxt[x][i]) fail[nxt[x][i]] = nxt[fail[x]][i], q.push(nxt[x][i]); else nxt[x][i] = nxt[fail[x]][i]; } } } inline void AC_Auto() { int p = 1, now = 0; while(p <= n) { now = nxt[now][id(str[p])]; int x = now; while(~x) { if (mark[x]) break; mark[x] = 1; x = fail[x]; } p++; } } inline int solve(int x) { int y = len[x]; int now = end[x]; while(now) { if (mark[now]) return y; y--; now = fa[now]; } return 0; } int main() { n = read(), m = read(); scanf("%s", str + 1); for (reg int i = 1 ; i <= m ; i ++) { scanf("%s", stt[i] + 1); ins(i); } AC_Match(); AC_Auto(); for (reg int i = 1 ; i <= m ; i ++) printf("%d\n", solve(i)); return 0; }
原文：https://www.cnblogs.com/BriMon/p/9569119.html