[COCI2011-2012#5] POPLOCAVANJE

|

卡常+分块+奇技淫巧能使AC自动机通过SAM黑题

传送门

首先不考虑空间的AC自动机的做法非常好想对吧,把每个单词都存好,匹配母串,打上标记即可。

但是AC自动机是存不了5000*5000的,但本题讨论中有大佬提供了一个做法,过10~30个字符串求一次答案并重建AC自动机。

但我觉得10~30个字符串非常草率,不如分个块,$\sqrt m$个串优美吧?

那就$\sqrt m$个串求一次答案,空间大概在6e5左右是比较稳的。但有一个坏消息,如果你AC自动机暴力跳fail+暴力打标记+没有优越的AC自动机模板的话,你就会T掉。

现在我来讲解一下一些优化技巧

预处理fail树

首先暴力跳fail是对复杂度影响最大的,我们给每个点附一个值cnt表示如果这个点是单词的结尾的话那个单词的长度,如果是多个就是最长的那个的长度。

我们跳fail实际上是求这个点到fail树根中最大的那个cnt,这个东西可以O(树的大小)处理出来。

那么有一个问题,如果在某点到fail树根的路径上,最大的cnt和某个比他小cnt的区间不同怎么办?(就是选了最大的那个cnt会导致小的cnt的区间计算不到)

不会出现这个情况,因为fail是由长的串指向跟当前串后缀相同的串,一定由长指向短,由母串指向子串,而且在一个点到根的路径上,cnt的最大值是递增的,比最大的cnt小的cnt代表的串一定作为当前串的子串出现过,所以比最大的cnt小的cnt一定曾被作为最大的cnt计算过

所以我们要把fail树建出来,对其dfs,匹配到一个点时O(1)得到他在到fail树根路径上最大的cnt。

差分打标记

如果你只会fail树而像一个刚学OI的萌新一样暴力打标记的话,那么说明你跟我一样AC自动机学傻了,这个trick是我在只有前面那个优化而T到85分时在神仙@ZUTTER_的代码里找到的,她暴力跳fail但用了这个优化成功的水了过去。

首先我们发现一个被标记打多少次是玄学的,如果你运气不好很可能被卡死,所以打标记的时候要改成对差分数组操作,在区间开头+1,在区间结尾后一位-1。最后做一遍前缀和,如果一个点是0那他一定没有被覆盖。

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
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#define re register
using namespace std;
struct node{
int ch[26],cnt,fail;
}t[600000];
struct edge{
int next,to;
}w[600001];
char ch[300001],s[5001]; int m;
int n,blo,heap,tail,team[600001];
int bl[5001],o[300001],num,cnt;
int maxn[600001],head[600001],ans;
inline void add(int x,int y){
w[++cnt].next=head[x];
w[cnt].to=y; head[x]=cnt;
}
inline void insert(char *s){
int u=0,l=strlen(s);
for (re int i=0; i<l; i++){
int a=s[i]-'a';
if (!t[u].ch[a]) t[u].ch[a]=++num;
u=t[u].ch[a];
}
t[u].cnt=l;
}
void dfs(int x){
maxn[x]=max(maxn[x],t[x].cnt);
for (re int i=head[x]; i; i=w[i].next){
maxn[w[i].to]=maxn[x]; dfs(w[i].to);
}
}
inline void build(){
heap=tail=1; team[heap]=0;
while (heap<=tail){
int x=team[heap];
for (re int i=0; i<26; i++){
if (t[x].ch[i]){
team[++tail]=t[x].ch[i];
if (!x) continue;
t[t[x].ch[i]].fail=t[t[x].fail].ch[i];
}
else t[x].ch[i]=t[t[x].fail].ch[i];
}
heap++;
}
memset(head,0,sizeof(head)); cnt=0;
for (re int i=1; i<=num; i++) add(t[i].fail,i);
dfs(0);
}
inline void change(){
int u=0;
for (re int i=1; i<=n; i++){
int a=ch[i]-'a'; u=t[u].ch[a];
// for (re int j=u; j; j=t[j].fail)
// if (t[j].cnt) o[i+1]-=1,o[i-t[j].cnt+1]+=1;
o[i+1]-=1; o[i-maxn[u]+1]+=1;
// for (re int j=0; j<maxn[u]; j++) o[i-j]=1;
}
}
int main(){
scanf("%d",&n); scanf("%s",ch+1);
scanf("%d",&m); blo=sqrt(m); bl[0]=1;
for (re int i=1; i<=m; i++) bl[i]=(i-1)/blo+1;
for (re int i=1; i<=m; i++){
scanf("%s",s); insert(s);
if (bl[i]!=bl[i-1]||i==m){
build(); change();
for (re int j=0; j<=num; j++){
t[j].cnt=t[j].fail=maxn[j]=0;
for (re int k=0; k<26; k++) t[j].ch[k]=0;
}
num=0;// puts("ok");
}
}
// for (re int i=1; i<=n; i++) if (!o[i]) ans++;
for (re int i=1; i<=n; i++){o[i]+=o[i-1]; if (!o[i]) ans++;}
printf("%d\n",ans);
return 0;
}

这份AC自动机代码大概只比正解慢1000ms,目前只有一个AC自动机跑的比我快。
听说调整块的大小能更快

文章目录
  1. 1. 预处理fail树
  2. 2. 差分打标记
,
载入天数...载入时分秒... 字数统计:75.7k