bzoj4566 [HAOI2016]找相同字符 [SAM]

写在前面

写这篇题解的原因纯粹是 zyt 神仙的方法太麻烦了

题目

luogu 3181

bzoj 4566

给定两个字符串,求出在两个字符串中各取出一个子串使得这两个子串相同的方案数。两个方案不同当且仅当这两
个子串中有一个位置不同。

$1 \leqslant length \leqslant 200000$

方法

可以直接跳到“简单来说”

对于有多个串的问题,我们可以建广义 $SAM$,但是实际上没有什么必要,可以将每两个串之间用一个奇怪的字符(例如 $’a’+26$)全部连起来,变成一个串,对于这个串建 $SAM$。

然后可以发现,如果这两个串有一个子串相同,那么这个子串在 $SAM$ 上对应的是同一个节点。我们转化一下,如果 $SAM$ 上的一个节点在串 $A$ 中的 $right$ 集合大小为 $a$,在串 $B$ 中的 $right$ 集合大小为 $b$,那么 $a$ ,$b$ 中任意两个配对都是一个合法的情况(即子串相同)。

又因为要求是本质不同的子串,$SAM$ 上每个节点代表了长度在 $[minlen,maxlen]$ 之间的相同的子串,故每个点的贡献还要乘上 $maxlen-minlen+1$。

简单来说,连接串 $A$,$B$ 建在一个 $SAM$ 上,如果用 $tot$ 表示 $SAM$ 的点数, $size[i][0/1]$ 表示 $SAM$ 上节点 $i$ 中包含的串 $A$ 或 $B$ 的 $right$ 集合的大小,$mx[i]$ 表示点 $i$ 的 $maxlen$,那么

代码

代码写起来就是 $SAM$ 的基础操作:插入和基数排序

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
#include<bits/stdc++.h>
using namespace std;

namespace TYC
{
const int N=800010;

long long ans;

namespace SAM
{
int last=1,tot=1,size[N][2];

struct node
{
int fa,mx,son[27];
}tr[N];

void insert(const int c,const int id)
{
int now=++tot,p=last;
tr[now].mx=tr[p].mx+1;
if(id!=2) size[now][id]++;
while(p&&!tr[p].son[c])
tr[p].son[c]=now,p=tr[p].fa;
if(!p) tr[now].fa=1;
else
{
int q=tr[p].son[c];
if(tr[q].mx==tr[p].mx+1) tr[now].fa=q;
else
{
int clone=++tot;
tr[clone]=tr[q];
tr[clone].mx=tr[p].mx+1;
tr[q].fa=tr[now].fa=clone;
while(p&&tr[p].son[c]==q)
tr[p].son[c]=clone,p=tr[p].fa;
}
}
last=now;
}

void radix_sort()
{
static int bask[N],q[N];
for(int i=1;i<=tot;i++) bask[tr[i].mx]++;
for(int i=1;i<=tot;i++) bask[i]+=bask[i-1];
for(int i=tot;i;i--) q[bask[tr[i].mx]--]=i;
for(int i=tot;i>1;i--)
{
int now=q[i],f=tr[now].fa;
size[f][0]+=size[now][0];
size[f][1]+=size[now][1];
ans+=(long long)size[now][0]*size[now][1]*(tr[now].mx-tr[f].mx);
}
}
}

void work()
{
static char s[N>>1];
scanf("%s",s);
int len=strlen(s);
for(int i=0;i<len;i++)
SAM::insert(s[i]-'a',0);
SAM::insert(26,2);
scanf("%s",s);
len=strlen(s);
for(int i=0;i<len;i++)
SAM::insert(s[i]-'a',1);
SAM::radix_sort();
printf("%lld",ans);
}
}

int main()
{
TYC::work();
return 0;
}