E
原题链接
大家都会ac自动机就我不会
本题目2500评分
大意
字符串$t$
和长$n$字符串列表 $s$
对于 所有$(i,j)$, 求s[i]+s[j]在t中的出现次数的和
数据范围
$|t|\le 200’000$
$n \le 200’000$
$|s_i| \in [1,200’000]$
$\sum |s_i| \le 200’000$
题解
显然
$ans = \sum \mathrm{suffix}i \cdot \mathrm{prefix}{i+1}$ 也就是 以$i$结尾匹配到 的次数 乘上$i+1$为开头匹配到的次数
那么问题来了，如何计算成功匹配的次数
引理 Aho–Corasick automaton
前置知识: Trie树, KMP
AC自动机 是什么?
答: 一种算法可以自动AC所有题目,多个模式同时匹配
AC自动机 从数据结构上看起来是个什么？
Trie Tree(字典树) + 匹配失败时的目标跳转指针(仿照KMP)
![trie tree and fail]()
对于字典建立的自动机
其中 后缀链接(suffix links/fail边)为蓝色, 字典后缀链接(dictionary suffix links)为绿色, 字典项为高亮蓝圆
建立Trie树
节点内容
1
2
3
4
5
| map<char,Node*> next 黑色边
cnt 蓝色圆(条目计数)
dep 长度/高度
fail 仿照kmp失配边, 绿色边
last 后缀链接 蓝色边
|
在建立过程中，结束的位置计数cnt++ (蓝色圆)
记录深度dep
计算next
建立 fail边
fail边的意义, 这来自于kmp中的fail, 假设当前为s, 则是指向s的最长后缀, 且为某个模式的前缀
1
2
3
4
5
| s: ????abcde
|
|
v
t: abcde 且t是某个最长前缀
|
默认值为所有fail边指向根节点
按深度(dep)从小到大广搜，
第一层节点的fail都指向根节点(一个字符更短的只有空字符串
每个节点的子节点扩展
p->next[charX] = p->fail->next[charX]
如果p->fail的后续节点没有charX呢? 实际上会递归fail(p->fail->fail->next[charX]),去找首个有charX的(和kmp里的一样)
匹配字符串
当建立完fail边就可以拿来匹配字符串了, 每次失去匹配通过fail进行跳转
建立last边
如何计数 当有 abba和bb的时候，如何能计数到bb?
每个节点增加一个last，指向 dep小于该节点的，存在的是该字串后缀的末节点。
这样的情况下，需要一条last，从a-b-b指向b-b的后一个b,其余节点的last指向根节点
所有last默认指向根节点
要是某个后缀，那么cnt>0,又要小于该字符串的最长的
则 ->fail(当->fail->cnt >0) 或->fail->last(->fail->cnt ==0 )
这样增加了last指针后，在匹配时，如果当前链下是后缀，则开始计数，如果不是则从当前->last开始计数
换句话说, last的本质是 把fail链上中间的cnt==0的点移除了, 只留了cnt>0的点和起始节点
递归代价? 复杂度分析?
fail边
不妨把fail 指针看到它指向的dep, 那么在树上, 显然每个点要么比它父节点指向的dep大1, 要么比父节点小, 每个从根到叶子的相邻变化和非负,且小于链长度, 正变化+|负变化| <= 2长度, 所以所有变化次数和 <= 2所有t的长度和, 和O(trie)建树一样的复杂度
当每层节点较少，比如只包含所有小写字母时，可以增加每层节点优化掉这递归过程
last边
很显然 每个点操作代价为常数 所以O(点 < sum |字典|)
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
| #include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
typedef long long ll;
const int MAX = 2e5+10;
struct AC_Automaton {
static const int K=26;
static const int MAX_NODE=2e5+10;
int getid(char c) {
return c-'a';
}
struct AC_NODE{
AC_NODE * next[K];
AC_NODE * fail;
AC_NODE * last;
int cnt;
int dep;
void init(AC_NODE * ac_n){
rep(i,0,K){
next[i] = ac_n;
}
fail = ac_n;
last = ac_n;
cnt = 0;
dep = 0;
}
}nodes[MAX_NODE];
AC_NODE * root;
int tot;
AC_NODE * newnode() {
nodes[tot].init(&nodes[0]);
return &nodes[tot++];
}
void init() {
tot=0;
root=newnode();
}
void insert(char *s) {
AC_NODE * now = root;
int len=strlen(s);
rep(i,0,len){
int t=getid(s[i]);
if(now->next[t] == root) {
now->next[t] = newnode();
now->next[t]->dep = i+1;
}
now=now->next[t];
}
now->cnt++;
}
void setfail() {
queue<AC_NODE *>q;
rep(i,0,K){
if(root->next[i] != root){
q.push(root->next[i]);
}
}
while(!q.empty()){
AC_NODE * now=q.front();
q.pop();
now->last = now->fail->cnt > 0 ? now->fail : now->fail->last;
rep(i,0,K){
if(now->next[i] != root) {
now->next[i]->fail=now->fail->next[i];
q.push(now->next[i]);
}else{
now->next[i]=now->fail->next[i];
}
}
}
}
ll be[MAX],en[MAX];
void work(char *s) {
int n = strlen(s);
AC_NODE * now = root;
rep(i,0,n+1){
be[i]=en[i]=0;
}
rep(i,0,n){
now=now->next[getid(s[i])];
AC_NODE * tmp = root;
if(now->cnt){
tmp=now;
}else if(now->last->cnt){
tmp=now->last;
}
while(tmp != root){
en[i]+=tmp->cnt;
if(i-tmp->dep+1>=0){
be[i-tmp->dep+1]+=tmp->cnt;
}
tmp=tmp->last;
}
}
ll ans=0;
rep(i,0,n-1){
ans+=en[i]*be[i+1];
}
printf("%lld\n",ans);
}
}ac;
char s[MAX],tmp[MAX];
int main() {
int q;
scanf("%s",s);
ac.init();
scanf("%d",&q);
while(q--) {
scanf("%s",tmp);
ac.insert(tmp);
}
ac.setfail();
ac.work(s);
return 0;
}
|
参考
https://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_algorithm
https://oi-wiki.org/string/ac-automaton/
TODO 抽个板子
