P3796 AC 自动机（简单版 II）
大意
询问那些模式串在文本串中出现的次数最多。
思路
依旧构建 AC 自动机，出现的次数通过不断跳 fail 统计即可。
代码
#include<iostream>
#include<queue>
#include<cstring>
#include<string>
using namespace std;const int MAXN = 1e6 + 5;
int ch[MAXN][26], idx = 0;
int fail[MAXN], n;
char c[MAXN];
string strs[155];
int id[MAXN], num[155];void reset() {idx = 0;memset(ch, 0, sizeof(ch));memset(fail, 0, sizeof(fail));memset(id, 0, sizeof(id));memset(num, 0, sizeof(num));
}void Insert(char *s, int pid){int now = 0;for(int i = 0;s[i];i ++){int x = s[i] - 'a';if(!ch[now][x]){ch[now][x] = ++ idx;}now = ch[now][x];}id[now] = pid;
}void build(){queue<int> q;for(int i = 0;i < 26;i ++){if(ch[0][i]){q.push(ch[0][i]);}}while(!q.empty()){int u = q.front(); q.pop();for(int i = 0;i < 26;i ++){if(ch[u][i]){fail[ch[u][i]] = ch[fail[u]][i];q.push(ch[u][i]);}else ch[u][i] = ch[fail[u]][i];}}
}void query(char *s){int now = 0;for(int k = 0;s[k];k ++){now = ch[now][s[k] - 'a'];for(int v = now;v;v = fail[v]){if(id[v]){num[id[v]] ++;}}}
}int main(){ios::sync_with_stdio(false);cin.tie(0);while(cin >> n, n){reset();for(int i = 1;i <= n;i ++){cin >> strs[i];Insert((char*)strs[i].c_str(), i);}build();cin >> c;query(c);int res = 0;for(int i = 1;i <= n;i ++) res = max(res, num[i]);cout << res << '\n';for(int i = 1;i <= n;i ++){if(num[i] == res) cout << strs[i] << '\n';}}return 0;
}