题目链接:P5357「【模板】AC自动机(二次加强版)」 。
给你一个文本串 S和 n 个模式串 T_{1..n},请你分别求出每个模式串 T_i 在 S 中出现的次数。
第一行包含一个正整数 n表示模式串的个数。
接下来 n 行,第 i行包含一个由小写英文字母构成的字符串 T_i 。
最后一行包含一个由小写英文字母构成的字符串 S 。
输出包含 n行,其中第 i行包含一个非负整数表示 T_i在 S中出现的次数。
5
a
bb
aa
abaa
abaaa
abaaabaa
6
0
3
2
1
1 \leq n \leq 2 \times 10^5,T_{1..n}的长度总和不超过2 \times 10^5,S 的长度不超过 2 \times 10^6 。
根据这种思路优化后的最坏复杂度降到了 O(n+m)。
#include <bits/stdc++.h>
using namespace std;
// AC 自动机
struct Automaton {
#ifndef _AUTOMATON_
#define ll int
#define MAXN 400005
#define MAXCHAR 26
#endif
ll cnt;
ll trie[MAXN][MAXCHAR];
ll exist[MAXN];
ll fail[MAXN];
ll mark[MAXN]; // 模式串编号
ll in[MAXN]; // 入度
Automaton(): cnt(0) {}
// 插入字符串
void insert(char *str, ll i) {
ll p = 0;
for(ll i = 0; str[i]; ++i) {
ll c = str[i] - 'a';
if(!trie[p][c]) {
trie[p][c] = ++cnt;
}
p = trie[p][c];
}
mark[i] = p;
}
// 构建失配指针
void build() {
queue <ll> q;
for(ll i = 0; i < MAXCHAR; ++i) {
if(trie[0][i]) {
q.push(trie[0][i]);
}
}
// BFS
while(q.size()) {
ll p = q.front();
q.pop();
for(ll i = 0; i < MAXCHAR; ++i) {
if(trie[p][i]) {
fail[trie[p][i]] = trie[fail[p]][i];
++in[trie[fail[p]][i]];
q.push(trie[p][i]);
} else {
trie[p][i] = trie[fail[p]][i];
}
}
}
}
// 匹配主串
void match(char *str) {
ll p = 0;
for(ll i = 0; str[i]; ++i) {
ll c = str[i] - 'a';
ll u = trie[p][c];
++exist[u];
p = trie[p][c];
}
}
// 计算所有模式串出现次数
void solve() {
queue <ll> q;
for(ll i = 1; i <= cnt; ++i) {
if(!in[i]) q.push(i);
}
while(q.size()) {
ll p = q.front();
q.pop();
if(fail[p]) {
exist[fail[p]] += exist[p];
--in[fail[p]];
if(!in[fail[p]]) q.push(fail[p]);
}
}
}
};
int main()
{
ll n;
static char str[MAXN*10];
static Automaton ac;
scanf("%d", &n);
for(ll i = 0; i < n; ++i) {
scanf("%s", str);
ac.insert(str, i);
}
scanf("%s", str);
ac.build();
ac.match(str);
ac.solve();
for(ll i = 0; i < n; ++i) {
printf("%d\n", ac.exist[ac.mark[i]]);
}
return 0;
}