隐藏
「bzoj3756」Pty的字符串 - 后缀自动机 | Bill Yang's Blog

路终会有尽头,但视野总能看到更远的地方。

0%

「bzoj3756」Pty的字符串 - 后缀自动机

题目大意

    给一颗每条边上有字符的trie树,再给一个长为$m$的字符串,求它的子串和树路径组成的字符串共有多少对匹配。
    $n\le800000, \left|S\right|\le8000000$


题目分析

正常解法是将串建成后缀自动机,Dfstrie树进行运行。
但因为串很长,建成后缀自动机空间量太大,考虑其他做法。

将trie树建成后缀自动机,将串在自动机中运行进行统计。
建立的方法有两种:

  • 每次插入时$last$返回新结点的父亲的$last$,套用以前的插入。(这是正确的,但是因为$\left|max\right|$有重复,故不能计数排序计算拓扑序,只能宽搜)
  • 每次插入时$last$返回新结点的父亲的$last$,将相同的转移合并起来。(时空间效率更高)

因为本题统计的需要算上重复,因此要统计$end_pos$集合并从上往下递推总数。
这里有讲过常见的后缀自动机模型。


代码

合并结点

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
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;

typedef long long LL;

inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}

const int maxn=800005,maxc=26;

struct SuffixAutomaton {
int cnt,root,last;
int next[maxn*2],Bucket[maxn*2],top[maxn*2];
LL Max[maxn*2],end_pos[maxn*2],sum[maxn*2];
int child[maxn*2][maxc];
SuffixAutomaton() {
cnt=0;
root=last=newnode(0);
}
int newnode(int val) {
cnt++;
next[cnt]=0;
Max[cnt]=val;
memset(child[cnt],0,sizeof(child[cnt]));
return cnt;
}
void insert(int data) {
if(child[last][data]) {
int p=last,old=child[last][data];
if(Max[old]==Max[p]+1) {
last=old;
end_pos[old]++;
} else {
int New=newnode(Max[p]+1);
last=New;
end_pos[New]=1;
copy(child[old],child[old]+maxc,child[New]);
next[New]=next[old];
next[old]=New;
for(; child[p][data]==old; p=next[p])child[p][data]=New;
}
} else {
int p=last,u=newnode(Max[last]+1);
last=u;
end_pos[u]=1;
for(; p&&!child[p][data]; p=next[p])child[p][data]=u;
if(!p)next[u]=root;
else {
int old=child[p][data];
if(Max[old]==Max[p]+1)next[u]=old;
else {
int New=newnode(Max[p]+1);
copy(child[old],child[old]+maxc,child[New]);
next[New]=next[old];
next[u]=next[old]=New;
for(; child[p][data]==old; p=next[p])child[p][data]=New;
}
}
}
}
void topsort() {
for(int i=1; i<=cnt; i++)Bucket[Max[i]]++;
for(int i=1; i<=cnt; i++)Bucket[i]+=Bucket[i-1];
for(int i=1; i<=cnt; i++)top[Bucket[Max[i]]--]=i;
}
void get_end_pos() {
topsort();
for(int i=cnt; i>=2; i--)end_pos[next[top[i]]]+=end_pos[top[i]];
}
void get_sum() {
get_end_pos();
end_pos[1]=0;
for(int i=2; i<=cnt; i++)sum[top[i]]=(Max[top[i]]-Max[next[top[i]]])*end_pos[top[i]]+sum[next[top[i]]];
}
LL run(string s) {
LL ans=0;
int now=root,len=0;
for(int x:s) {
int ch=x-'a';
while(now&&!child[now][ch]) {
now=next[now];
len=Max[now];
}
if(!now) {
now=root;
len=0;
} else {
now=child[now][ch];
len++;
}
ans+=sum[next[now]]+(len-Max[next[now]])*end_pos[now];
}
return ans;
}
} sam;

int n,m,Hash[maxn];
char s[maxn];

int main() {
n=Get_Int();
Hash[1]=1;
for(int i=2; i<=n; i++) {
int x=Get_Int();
char ch=' ';
while(!isalpha(ch))ch=getchar();
sam.last=Hash[x];
sam.insert(ch-'a');
Hash[i]=sam.last;
}
sam.get_sum();
scanf("%s",s);
printf("%lld\n",sam.run(s));
return 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
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
117
118
119
120
121
122
123
124
125
126
127
128
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;

typedef long long LL;

inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}

const int maxn=800005,maxc=26;

struct SuffixAutomaton {
int cnt,root,last;
int next[maxn*2],InDegree[maxn*2],top[maxn*2];
LL Max[maxn*2],end_pos[maxn*2],sum[maxn*2];
int child[maxn*2][maxc];
SuffixAutomaton() {
cnt=0;
root=last=newnode(0);
}
int newnode(int val) {
cnt++;
next[cnt]=0;
Max[cnt]=val;
memset(child[cnt],0,sizeof(child[cnt]));
return cnt;
}
void insert(int data) {
int p=last,u=newnode(Max[last]+1);
last=u;
end_pos[u]=1;
for(; p&&!child[p][data]; p=next[p])child[p][data]=u;
if(!p)next[u]=root;
else {
int old=child[p][data];
if(Max[old]==Max[p]+1)next[u]=old;
else {
int New=newnode(Max[p]+1);
copy(child[old],child[old]+maxc,child[New]);
next[New]=next[old];
next[u]=next[old]=New;
for(; child[p][data]==old; p=next[p])child[p][data]=New;
}
}
}
void topsort() {
queue<int>Q;
for(int i=2; i<=cnt; i++)InDegree[next[i]]++;
for(int i=1; i<=cnt; i++)
if(!InDegree[i])Q.push(i);
int tot=0;
while(!Q.empty()) {
int now=Q.front();
top[++tot]=now;
Q.pop();
if(--InDegree[next[now]]==0)Q.push(next[now]);
}
reverse(top+1,top+tot+1);
}
void get_end_pos() {
topsort();
for(int i=cnt; i>=2; i--)end_pos[next[top[i]]]+=end_pos[top[i]];
}
void get_sum() {
get_end_pos();
end_pos[1]=0;
for(int i=2; i<=cnt; i++)sum[top[i]]=(Max[top[i]]-Max[next[top[i]]])*end_pos[top[i]]+sum[next[top[i]]];
}
LL run(string s) {
LL ans=0;
int now=root,len=0;
for(int x:s) {
int ch=x-'a';
while(now&&!child[now][ch]) {
now=next[now];
len=Max[now];
}
if(!now) {
now=root;
len=0;
} else {
now=child[now][ch];
len++;
}
ans+=sum[next[now]]+(len-Max[next[now]])*end_pos[now];
}
return ans;
}
} sam;

int n,m,Hash[maxn];
char s[maxn];

int main() {
n=Get_Int();
Hash[1]=1;
for(int i=2; i<=n; i++) {
int x=Get_Int();
char ch=' ';
while(!isalpha(ch))ch=getchar();
sam.last=Hash[x];
sam.insert(ch-'a');
Hash[i]=sam.last;
}
sam.get_sum();
scanf("%s",s);
printf("%lld\n",sam.run(s));
return 0;
}

姥爷们赏瓶冰阔落吧~