【BZOJ4566】【HAOI2016】找相同字符

发表于 | 分类于 ， | 评论数： | 阅读次数：
继续讲述LCP与单调栈的妙用

1

题解

知识点：

后缀数组，LCP，单调栈

分析：

要求两个串的子串相同的个数，在两个串上不是很好求。所以我们转换成一个串，把两个串连接成一个字符串，我们要求两个串的后缀的前缀相同的个数（而且这两个位置必须得来自两个不同的串，当然这个只是一个简单的判断而已）。

把串连接起来之后，做两遍单调栈，分别枚举前面的对后面的做的贡献。而两遍单调栈分别以A串和B串作为主元（哪个为主，前缀和贡献的时候就算哪一个，而在代码中的贡献判断就算另一个）。

这样整个过程的时间复杂度是$O(n\log_{2}n)$的。

代码：

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
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;

const int maxn=400010;
int n,m,sa[maxn],rnk[maxn],y[maxn],height[maxn],pos,c[maxn],len,sum[maxn];
typedef long long ll;
ll ans,tmp;
struct node
{
	int x,ht;
}st[maxn];
char s[maxn];

void srt()
{
	int i;
	memset(c,0,sizeof(c));
	for (i=1;i<=n;i++)
		c[rnk[i]]++;
	for (i=2;i<=m;i++)
		c[i]+=c[i-1];
	for (i=n;i>=1;i--)
		sa[c[rnk[y[i]]]--]=y[i];
}

void getsa()
{
	int i,p=0,k;
	m=122;
	for (i=1;i<=n;i++)
	{
		rnk[i]=s[i]-96;
		y[i]=i;
	}
	srt();
	for (k=1;p<n;k<<=1,m=p)
	{
		p=0;
		for (i=n-k+1;i<=n;i++)
			y[++p]=i;
		for (i=1;i<=n;i++)
			if (sa[i]>k)
				y[++p]=sa[i]-k;
		srt();
		swap(rnk,y);
		rnk[sa[1]]=p=1;
		for (i=2;i<=n;i++)
			rnk[sa[i]]=(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k])?p:++p;
	}
}

void getheight()
{
	int i,j,k=0;
	for (i=1;i<=n;i++)
	{
		if (k)
			k--;
		j=sa[rnk[i]-1];
		while (s[i+k]==s[j+k])
			k++;
		height[rnk[i]]=k;
	}
}

int main()
{
	int i,j;
	scanf("%s",s+1);
	len=strlen(s+1);
	s[len+1]='z'+1;//放一个一定最大的不在字符集中的字符，不会影响整个串
	scanf("%s",s+len+2);
	n=strlen(s+1);
	getsa();
	getheight();
	st[pos]=(node){1,0};
	for (i=1;i<=n;i++)
		sum[i]+=sum[i-1]+(sa[i]<=len);//前缀和贡献的个数
	for (i=1;i<=n;i++)
	{
		while (height[i]<height[st[pos].x]&&pos)
			pos--;
		st[++pos]=(node){i,(sum[i-1]-sum[st[pos-1].x-1])*height[i]+st[pos-1].ht};//贡献
		if (sa[i]>len+1)
			ans+=st[pos].ht;
	}
	pos=0;
	memset(sum,0,sizeof(sum));//与上面的过程同理
	for (i=1;i<=n;i++)
		sum[i]+=sum[i-1]+(sa[i]>len+1);
	for (i=1;i<=n;i++)
	{
		while (height[i]<height[st[pos].x]&&pos)
			pos--;
		st[++pos]=(node){i,(sum[i-1]-sum[st[pos-1].x-1])*height[i]+st[pos-1].ht};
		if (sa[i]<=len)
			ans+=st[pos].ht;
	}
	printf("%lld\n",ans);
	return 0;
}

顺便讲一讲罗穗骞的论文中讲到的眼神问题，如果规定要求的答案是两个串的长度大于等于$k$的子串的个数，那么在单调栈前还要做一些改动，就是将height值按照能不能大于等于$k$进行分组，分完组之后，贡献就只能在组内算，不能算外面的（因为那些长度都不够）。详情见论文。

显示 Gitment 评论