题目传送门
-------------------------------------- 过年在家无聊补一下这周做的几道AC自动机的模板题
sol:AC自动机,在fail边的基础上再加一个last边,指向真正有效的节点,跳fail边改成跳last边来跳过无效点。
- AC自动机
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int MAXN = ;
struct Trie {
int son[MAXN][], fail[MAXN], last[MAXN];
int cnt[MAXN], inde[MAXN]; int tot, root, _max;
vector<int> vec; string str[];
int add_node() {
memset(son[tot], -, sizeof(son[tot]));
cnt[tot] = ; inde[tot] = -;
return tot ++;
}
void init() {
tot = _max = ;
root = add_node();
}
void insert(char* s, int id) {
int p = root;
for (int i = ; s[i]; i++) {
int index = s[i] - 'a';
if (son[p][index] == -)
son[p][index] = add_node();
p = son[p][index];
}
inde[p] = id;
str[id] = s;
}
void build() {
queue<int> que;
fail[root] = last[root] = root;
for (int i = ; i < ; i++) {
if (son[root][i] == -) son[root][i] = root;
else {
fail[son[root][i]] = root;
last[son[root][i]] = root;
que.push(son[root][i]);
}
}
while (!que.empty()) {
int p = que.front(); que.pop();
for (int i = ; i < ; i++) {
if (son[p][i] == -) son[p][i] = son[fail[p]][i];
else {
fail[son[p][i]] = son[fail[p]][i];
if (inde[son[fail[p]][i]] != -)
last[son[p][i]] = son[fail[p]][i];
else
last[son[p][i]] = son[last[p]][i];
que.push(son[p][i]);
}
}
}
}
void slove(char* s) {
int p = root;
for (int i = ; s[i]; i++) {
int index = s[i] - 'a';
p = son[p][index];
for (int tmp = p; tmp != root; tmp = last[tmp]) {
if (inde[tmp] == -) continue;
cnt[tmp] ++;
if (cnt[tmp] > _max) {
_max = cnt[tmp];
vec.clear();
vec.push_back(inde[tmp]);
} else if (cnt[tmp] == _max) {
vec.push_back(inde[tmp]);
}
}
}
}
void output() {
printf("%d\n", _max);
sort(vec.begin(), vec.end());
for (int i = ; i < vec.size(); i++)
cout << str[vec[i]] << endl;
}
} ac;
char s[];
int main() {
int n;
while (scanf("%d", &n) && n) {
ac.init();
for (int i = ; i <= n; i++) {
scanf("%s", s);
ac.insert(s, i);
}
ac.build(); scanf("%s", s);
ac.slove(s); ac.output();
}
return ;
}