考虑 trie 树上像 kmp 一样设置 fail 指针。例如匹配 \(abcd\) 的时候失配了跳回去 \(bcd\) 那里。
用 BFS 的方法进行跳转，如果 \(i\) 是 \(j\) 在 trie 树上的父亲，那么如果 \(fail_i\) 存在延伸出去的 \(c\) 边，那么 \(fail_j = fail_i.ed_c\)。否则继续往回跳直到 \(0\)。
实现上，先把 trie 建好，然后 build 的时候直接把不存在的边设置为该节点 \(fail\) 节点的对应边。这样每一个节点都会直接找到其 \(faik\) 指针。
注意一开始的两层，要直接设置，也就是 \(i=0\) 的时候要特判，否则死循环。
P3808
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define f(i, a, b) for(int i = (a); i <= (b); i++)
#define cl(i, n) i.clear(),i.resize(n);
#define endl '\n'
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
const int inf = 1e9;
void cmax(int &x, int y) {if(x < y) x = y;}
void cmin(int &x, int y) {if(x > y) x = y;}
//调不出来给我对拍！
string s[1001000];
struct node {
int fail;
int tag;
int ed[26];
}t[1000010];
int cnt = 0;
void add(string k) {
int cur = 0;
f(i, 0, (int)k.size() - 1) {
if(!t[cur].ed[k[i] - 'a']) {
t[cur].ed[k[i] - 'a'] = ++cnt;
}
cur = t[cur].ed[k[i] - 'a'];
}
t[cur].tag ++;
}
void build() {
queue<int> q; q.push(0);
while(!q.empty()) {
int cur = q.front(); q.pop();
f(i, 0, 25) {
if(!t[cur].ed[i]) {
t[cur].ed[i] = t[t[cur].fail].ed[i];
continue;
}
q.push(t[cur].ed[i]);
int nxt = t[cur].ed[i];
if(cur == 0) t[nxt].fail = 0;
else {
t[nxt].fail = t[t[cur].fail].ed[i];
}
}
}
}
void query(string m) {
int cur = 0, match = 0;
for(char ch : m) {
cur = t[cur].ed[ch - 'a'];
match += t[cur].tag;
t[cur].tag = 0;
}
cout << match <<endl;
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(NULL);
cout.tie(NULL);
//time_t start = clock();
//think twice,code once.
//think once,debug forever.
int n; cin >> n;
f(i, 1, n) cin >> s[i];
f(i, 1, n) add(s[i]);
build();
string m; cin >> m;
query(m);
//time_t finish = clock();
//cout << "time used:" << (finish-start) * 1.0 / CLOCKS_PER_SEC <<"s"<< endl;
return 0;
}
功能：
首先可以记录文本串经过每一个点的次数，其和为文本串长度。
然后如果要统计一个模式串的出现次数怎么办？直接在点上打标记吗？不！因为当一个模式串是另一个模式串的子串的时候，只会统计一个。例如下图，走到节点 \(i\) 的时候只会统计 \(\mathtt {aabb}\) 的次数，不会统计 \(\mathtt {ab}\) 的次数。
怎么办？考虑 fail 树上的节点，对于一个串，如果有一次出现，那么一定出现在 fail 树上其本身节点或其本身节点的子树内某一个位置。我们在这个位置计算一次。
例如这样，到 \(4\) 节点的时候会算一次 \(\mathtt{ab}\)。
怎么实现？每个节点统计祖先里面一共多少个串 \(i\)？显然不可能，这样退化到 \(O(n |s|)\)。
其实匹配的时候还是统计每个点走了几次，然后最后来树形 DP 就可以了。
代码：（P3796）
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define f(i, a, b) for(int i = (a); i <= (b); i++)
#define cl(i, n) i.clear(),i.resize(n);
#define endl '\n'
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
const int inf = 1e9;
void cmax(int &x, int y) {if(x < y) x = y;}
void cmin(int &x, int y) {if(x > y) x = y;}
//调不出来给我对拍！
int n;
string s[155];
struct node {
int ed[26];
int tag;
int fail;
node(){memset(ed,0,sizeof(ed));tag=fail=0;}
}t[155 * 75];
int cnt = 0;
int pass[155 * 75];
int exist[155];
vector<int> son[155 * 75];
void add(string str, int ind) {
int cur = 0;
for(char ch : str) {
if(!t[cur].ed[ch - 'a'] ) t[cur].ed[ch - 'a'] = ++cnt;
cur = t[cur].ed[ch - 'a'];
}
t[cur].tag = ind;
}
void build() {
queue<int> q; q.push(0);
while(!q.empty()) {
int cur = q.front(); q.pop();
f(i, 0, 25) {
if(!t[cur].ed[i]) {
t[cur].ed[i] = t[t[cur].fail].ed[i];
continue;
}
q.push(t[cur].ed[i]);
if(cur == 0) t[t[cur].ed[i]].fail = 0;
else t[t[cur].ed[i]].fail = t[t[cur].fail].ed[i];
son[t[t[cur].ed[i]].fail].push_back(t[cur].ed[i]);
}
}
}
void match(string tar) {
int cur = 0;
for(char ch : tar) {
cur = t[cur].ed[ch - 'a'];
// cout << t[cur].tag << endl;
pass[cur] ++;
}
}
bitset<155> bs[155 * 75];
void dfs(int now) {
// cout << now << " " << pass[now] << endl;
if(t[now].tag != 0) bs[now][t[now].tag] = 1;
// f(i, 1, n) cout << bs[now][i];
// cout<<endl;
f(i, 1, n) exist[i] += pass[now] * bs[now][i];
for(int i : son[now]) {
bs[i] |= bs[now];
dfs(i);
}
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(NULL);
cout.tie(NULL);
//time_t start = clock();
//think twice,code once.
//think once,debug forever.
while(cin >> n && n > 0) {
f(i, 1, n) exist[i] = 0;
cnt = 0;
f(i, 0, n * 71) t[i] = node();
f(i, 0, n * 71) son[i].clear();
f(i, 1, n) { cin >> s[i]; }
f(i, 1, n) { add(s[i], i); }
build();
string tar; cin >> tar;
f(i, 0, cnt) pass[i] = 0;
match(tar);
f(i, 0, cnt) bs[i].reset();
// f(i, 1, n) exist[i] = 0;
dfs(0);
int mxt = 0;
f(i, 1, n) cmax(mxt, exist[i]);
cout << mxt << endl;
f(i, 1, n) {if(exist[i] == mxt) cout << s[i] << endl;}
}
//time_t finish = clock();
//cout << "time used:" << (finish-start) * 1.0 / CLOCKS_PER_SEC <<"s"<< endl;
return 0;
}