大致步骤：
一：Trie插入 {
遍历字符串，有节点就进入节点，没有节点就创建节点后进入节点。
}
二：构建fail指针 {
fail指向当前Trie中含有的最长后缀字符串。
BFS遍历每一层
动归思想：{
对当前这一层的某个节点x，找到其父节点的fail所指的节点y (这样可以保证x前面一段的最长前缀，也就是之前的状态)，如果当前节点y下有x，那么x的fail指向y，否则一直跳fail直到root。
}
}
三：查询 {
遍历字符串，能匹配则继续，不然一直跳fail直到root
}
模板：总共n个t串，求s串中包含的t串的数目。
#pragma GCC optimize(2) #include <cstdio> #include <iostream> #include <cstring> #include <cstdlib> #include <vector> #include <map> #include <unordered_map> #include <set> #include <queue> #include <deque> #include <list> #include <climits> #include <bitset> #include <fstream> #include <algorithm> #include <functional> #include <stack> #include <string> #include <cmath> #define fi first #define se second #define re register #define ls i << 1 #define rs i << 1 | 1 #define pb push_back #define pii pair<int,int> #define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); #define mod 10007 //#define int long long using namespace std; typedef long long ll; typedef unsigned long long ull; const double eps = 1e-8; const int inf = 0x3f3f3f3f; const long long INF = 0x3f3f3f3f3f3f3f3f; const double pi = acos(-1.0); int tt; inline int rd(){ int x = 0, f = 1; char ch = getchar(); while (ch < ‘0‘ || ch>‘9‘) { if (ch == ‘-‘)f = -1; ch = getchar(); } while (ch >= ‘0‘ && ch <= ‘9‘) { x = x * 10 + ch - ‘0‘; ch = getchar(); } return x * f; } void out(int a) { if (a < 0) putchar(‘-‘), a = -a; if (a >= 10) out(a / 10); putchar(a % 10 + ‘0‘); } queue<int> q; const int N = 1e6+10; char s[N], t[55]; int idx, ans; struct Trie{ int son[26]; int fail = -1, cnt = 0; int flag = 0; }; vector<Trie> node; void ins(char* s) { int p = 0, len = strlen(s); for (int i = 0; i < len; i++) { int now = s[i] - ‘a‘; if (!node[p].son[now]) node[p].son[now] = ++idx; p = node[p].son[now]; } node[p].cnt++; } void getfail() { while (!q.empty()) q.pop(); for (int i = 0; i < 26; i++) { if (node[0].son[i]) { int son = node[0].son[i]; node[son].fail = 0; q.push(son); } } while (!q.empty()) { int f = q.front(); q.pop(); for (int i = 0; i < 26; i++) { if (node[f].son[i]) { int now = node[f].son[i]; int fafail = node[f].fail; while (~fafail && !node[fafail].son[i]) fafail = node[fafail].fail; if (~fafail) node[now].fail = node[fafail].son[i]; else node[now].fail = 0; q.push(now); } } } } void query(char* t) { int p = 0, len = strlen(t); for (int i = 0; i < len; i++) { int word = t[i] - ‘a‘; while (!node[p].son[word] && ~node[p].fail) p = node[p].fail; if (node[p].son[word]) p = node[p].son[word]; else continue; int p2 = p; while (~node[p2].fail) { if (node[p2].flag) break; node[p2].flag = 1; ans += node[p2].cnt; p2 = node[p2].fail; } } } void solve() { node.clear(); node.resize(1000005); idx = ans = 0; int n = rd(); for (int i = 1; i <= n; i++) scanf("%s",t),ins(t); getfail(); scanf("%s",s); query(s); printf("%d\n",ans); } signed main(){ for (int tt = rd(); tt--;) solve(); return 0; }
原文：https://www.cnblogs.com/hznudreamer/p/13584103.html