NKOJ 4151 （TJOI 2016&HEOI 2016）字符串（后缀数组+倍增+主席树）

发表于 |
字数统计: 1,343字 | 阅读时长 ≈ 7min

【Tjoi2016&Heoi2016】字符串

问题描述

佳媛姐姐过生日的时候，她的小伙伴从某东上买了一个生日礼物。生日礼物放在一个神奇的箱子中。箱子外边写了一个长为n的字符串s，和m个问题。佳媛姐姐必须正确回答这m个问题，才能打开箱子拿到礼物，升职加薪，出任CEO，嫁给高富帅，走上人生巅峰。每个问题均有a,b,c,d四个参数，问你子串s[a..b]的所有子串和s[c..d]的最长公共前缀的长度的最大值是多少？佳媛姐姐并不擅长做这样的问题，所以她向你求助，你该如何帮助她呢？

输入格式

输入的第一行有两个正整数n,m，分别表示字符串的长度和询问的个数。接下来一行是一个长为n的字符串。接下来m行，每行有4个数a,b,c,d，表示询问s[a..b]的所有子串和s[c..d]的最长公共前缀的最大值。

输出格式

对于每一次询问，输出答案。

样例输入

5 5
aaaaa
1 1 1 5
1 5 1 1
2 3 2 3
2 4 2 3
2 3 2 4

样例输出

1
1
2
2
2

提示

1<=n,m<=100,000,字符串中仅有小写英文字母，a<=b,c<=d,1<=a,b,c,d<=n

此题思路比较直接，考虑到直接搞的麻烦，考虑二分答案，那么问题可以转化成求$[a,b-mid+1]$中是否存在一个位置开始的后缀与以$c$为开头的后缀的最长公共前缀大于$mid$

考虑如何判断，考虑SA数组，显然与c开头的后缀最长公共前缀大于$mid$的后缀在SA数组中是连续的一个区间，那么问题即是求是否存在以$[a,b-mid+1]$开头的后缀在SA数组中的位置恰好在上述区间中，那么用主席树维护每个位置对应$SA$数组中出现位置的情况，直接查找即可。

关于找出区间，RMQ处理Height数组，然后倍增查找即可。

代码：

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
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#define N 200005
#define M 10000005
using namespace std;
char s[N];
int n,m,SA[N],Rank[N],H[N],F[N][20],S=18;
int wa[N],wb[N],T[N];
int tot,ls[M],rs[M],v[M],rt[N];
bool equ(int *r,int a,int b,int l)
{return r[a]==r[b]&&r[a+l]==r[b+l];}
void GSA(char *r,int *sa,int a,int b)
{
	int i,j,p,*x=wa,*y=wb,*t;
	for(i=0;i<b;i++)T[i]=0;
	for(i=0;i<a;i++)T[x[i]=r[i]]++;
	for(i=1;i<b;i++)T[i]+=T[i-1];
	for(i=a-1;i>=0;i--)sa[--T[x[i]]]=i;
	for(p=1,j=1;p<a;j<<=1,b=p)
	{
		for(p=0,i=a-j;i<a;i++)y[p++]=i;
		for(i=0;i<a;i++)if(sa[i]>=j)y[p++]=sa[i]-j;
		for(i=0;i<b;i++)T[i]=0;
		for(i=0;i<a;i++)T[x[y[i]]]++;
		for(i=1;i<b;i++)T[i]+=T[i-1];
		for(i=a-1;i>=0;i--)sa[--T[x[y[i]]]]=y[i];
		for(t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1;i<a;i++)
		x[sa[i]]=equ(y,sa[i-1],sa[i],j)?p-1:p++;
	}
}
void GH(char *r,int *sa,int a)
{
	int i,j,k=0;
	for(i=1;i<=a;i++)Rank[sa[i]]=i;
	for(i=0;i<a;H[Rank[i++]]=k)
	for(k?k--:0,j=sa[Rank[i]-1];r[i+k]==r[j+k];k++);
}
void RMQ()
{
	int i,j;
	for(i=1;i<=n;i++)F[i][0]=H[i];
	for(i=n;i>=1;i--)
	for(j=1;i+(1<<j-1)<=n;j++)
	F[i][j]=min(F[i][j-1],F[i+(1<<j-1)][j-1]);
}
int CP(int x)
{
	int p=++tot;
	ls[p]=ls[x];
	rs[p]=rs[x];
	v[p]=v[x];
	return p;
}
int ADD(int p,int l,int r,int k)
{
	int o=CP(p);
	if(l==r){v[o]++;return o;}
	int mid=l+r>>1;
	if(k<=mid)ls[o]=ADD(ls[o],l,mid,k);
	else rs[o]=ADD(rs[o],mid+1,r,k);
	v[o]=v[ls[o]]+v[rs[o]];
	return o;
}
int GS(int lp,int rp,int l,int r,int x,int y)
{
	if(x<=l&&y>=r)return v[rp]-v[lp];
	int mid=l+r>>1,cs=0;
	if(x<=mid&&y>=l)cs+=GS(ls[lp],ls[rp],l,mid,x,y);
	if(x<=r&&y>mid)cs+=GS(rs[lp],rs[rp],mid+1,r,x,y);
	return cs;
}
bool ok(int t,int a,int b,int c)
{
	int l=Rank[c],r=Rank[c];
	for(int i=S;i>=0;i--)
	{
		if(l-(1<<i)>=0&&F[l-(1<<i)+1][i]>=t)l=l-(1<<i);
		if(r+(1<<i)<=n&&F[r+1][i]>=t)r=r+(1<<i);
	}
	return GS(rt[a-1],rt[b],1,n,l,r);
}
void EF(int l,int r,int a,int b,int c)
{
	int mid;
	while(l<=r)
	{
		mid=l+r>>1;
		if(ok(mid,a,b-mid+1,c))l=mid+1;
		else r=mid-1;
	}
	printf("%d\n",r);
}
int main()
{
	int a,b,c,d;
	scanf("%d%d%s",&n,&m,s);s[n]='a'-1;
	GSA(s,SA,n+1,200);GH(s,SA,n);RMQ();
	rt[0]=ADD(rt[0],1,n,Rank[0]);
	for(int i=1;i<n;i++)rt[i]=ADD(rt[i-1],1,n,Rank[i]);
	while(m--)
	{
		scanf("%d%d%d%d",&a,&b,&c,&d);
		a--;b--;c--;d--;
		EF(1,min(b-a+1,d-c+1),a,b,c);
	}
}