BZOJ4566 [HAOI2016]找相同字符(后缀数组)

题目链接

洛谷

dark bzoj

题意简述

给你两个字符串,从中各取一个子串使这两个子串相同,求方案数。

简要做法

以某两个位置开头的相同子串数=这两个位置开头的后缀的 $lcp$

如果在同一个字符串中,求出 height 数组后使用单调栈求出每个位置作为最小值的贡献即可(单调栈部分与 P2659 美丽的序列[ZJOI2007]棋盘制作 等题类似,在此就不赘述了;求两两 $lcp​$ 之和这部分与 [AHOI2013]差异 类似,故没有写那题的题解)。

由于有两个字符串不太方便,考虑将它们拼接起来并在中间加上一个不存在的字符(如#)。这样求出拼接后的字符串的答案,减去两个原串的答案,就是最终的答案。

参考代码

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int N=400010;

typedef long long ll;

int sa[N],sa2[N<<1],rk[N<<1],px[N],cnt[N],sta[N],top,f[N],height[N];

struct Suffix_Array
{
char s[N];
ll calc()
{
ll out=0;
int n,i,k,w,p,m=200;
n=strlen(s+1);
memset(sa2,0,sizeof(sa2));
memset(cnt,0,sizeof(cnt));
for (i=1;i<=n;++i) ++cnt[rk[i]=s[i]];
for (i=1;i<=m;++i) cnt[i]+=cnt[i-1];
for (i=n;i>=1;--i) sa[cnt[rk[i]]--]=i;
for (w=1;w<n;w<<=1,m=p)
{
memset(cnt,0,sizeof(cnt));
for (p=0,i=n;i>n-w;--i) sa2[++p]=i;
for (i=1;i<=n;++i) if (sa[i]>w) sa2[++p]=sa[i]-w;
for (i=1;i<=n;++i) ++cnt[px[i]=rk[sa2[i]]];
for (i=1;i<=m;++i) cnt[i]+=cnt[i-1];
for (i=n;i>=1;--i) sa[cnt[px[i]]--]=sa2[i];
swap(rk,sa2);
for (p=0,i=1;i<=n;++i) rk[sa[i]]=sa2[sa[i]]==sa2[sa[i-1]]&&sa2[sa[i]+w]==sa2[sa[i-1]+w]?p:++p;
}
for (i=1,k=0;i<=n;++i)
{
if (k) --k;
while (s[i+k]==s[sa[rk[i]-1]+k]) ++k;
height[rk[i]]=k;
}
for (i=1;i<=n;++i)
{
while (top&&height[sta[top]]>=height[i]) --top;
f[i]=i-sta[top];
sta[++top]=i;
}
top=0;
sta[++top]=n+1;
height[n+1]=0;
for (i=n;i>=1;--i)
{
while (top&&height[sta[top]]>height[i]) --top;
out+=(ll)f[i]*(sta[top]-i)*height[i];
sta[++top]=i;
}
return out;
}
} a,b,ab;

int main()
{
int n,m,i;

scanf("%s%s",a.s+1,b.s+1);

n=strlen(a.s+1);
m=strlen(b.s+1);
for (i=1;i<=n;++i) ab.s[i]=a.s[i];
ab.s[n+1]='#';
for (i=1;i<=m;++i) ab.s[n+1+i]=b.s[i];

cout<<ab.calc()-a.calc()-b.calc();

return 0;
}