「Luogu2743/POJ1743」[USACO5.1]乐曲主题Musical Themes

Luogu
Poj

两个OJ题号的LCS长度为3

Solution

洛谷这边NN的范围是50005000，哈希可以过

但是在POJ就到了2000020000，而且是多组数据，哈希似乎是过不了了

这里写一下用后缀数组的一个比较妙的做法

首先，对于转调的情况，我们很容易想到可以对原数组进行差分

然后做SASA，求出差分数组的heightheight

显然答案可以二分，我们二分答案midmid，然后将heightheight数组分成若干段。对于每一段height[x]height[x]到height[y]height[y]，满足height[x+1]height[x+1]到height[y]height[y]均大于等于midmid

我们知道，对于两个后缀x,yx,y，lcp(x,y)=min{height[rank[x+1]],height[rank[x+2]],…,height[rank[y]]}lcp(x,y)=min\{height[rank[x+1]],height[rank[x+2]],\dots,height[rank[y]]\}

所以在每一段中，任意两个被划分到同一段的后缀的lcplcp长度都是大于等于midmid的

那么在每一段内，若存在一对(i,j)(i,j)满足sa[j]−sa[i]>midsa[j]-sa[i]>mid，那么这个midmid就是合法的

长度不小于55可以通过调整二分的下界进行限制

需要注意的是我们是对差分数组进行处理，所以原序列的子串的长度==对应差分序列子串长度+1+1

Code

这里放的是POJPOJ的ACAC代码

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
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
typedef long long ll;

template <typename T>void read(T &t)
{
	t=0;int f=0;char c=getchar();
	while(!isdigit(c)){f|=c=='-';c=getchar();}
	while(isdigit(c)){t=t*10+c-'0';c=getchar();}
	if(f)t=-t;
}

const int maxn=20000+5;
int n,m;
int det[maxn];
int sa[maxn],rnk[maxn],tp[maxn];

int c[maxn];
void Sort()
{
	for(register int i=0;i<=m;++i)c[i]=0;
	for(register int i=1;i<=n;++i)c[rnk[i]]++;
	for(register int i=1;i<=m;++i)c[i]+=c[i-1];
	for(register int i=n;i;--i)sa[c[rnk[tp[i]]]--]=tp[i];
}

int height[maxn];
void GetHeight()
{
	for(register int i=1;i<=n;++i)rnk[i]=det[i],tp[i]=i;
	Sort();
	for(register int w=1,p=0;p<n;m=p,w<<=1)
	{
		p=0;
		for(register int i=1;i<=w;++i)tp[++p]=n-w+i;
		for(register int i=1;i<=n;++i)if(sa[i]>w)tp[++p]=sa[i]-w;
		Sort();
		swap(tp,rnk);
		rnk[sa[1]]=1,p=1;
		for(register int i=2;i<=n;++i)
			rnk[sa[i]]=(tp[sa[i]]==tp[sa[i-1]] && tp[sa[i]+w]==tp[sa[i-1]+w])?p:++p;
	}
	for(register int i=1,k=0;i<=n;++i)
	{
		if(k)--k;
		int j=sa[rnk[i]-1];
		while(det[i+k]==det[j+k])++k;
		height[rnk[i]]=k;
	}
}

bool Check(int len)
{
	int xx;
	for(register int i=1;i<=n;i=xx+1)
	{
		xx=i;
		while(height[xx+1]>=len)++xx;
		int mn=0x3f3f3f3f,mx=0;
		for(register int j=i;j<=xx;++j)
		{
			mn=min(mn,sa[j]);
			mx=max(mx,sa[j]);
		}
		if(mx-mn>len)return true;
	}
	return false;
}

int main()
{
	while(scanf("%d",&n),n)
	{
		m=88*2;
		for(register int i=1,last=0;i<=n;++i)
		{
			int x;
			read(x);
			det[i]=x-last+88;//防止出现负数
			last=x;
		}
		GetHeight();
		register int l=4,r=n-1,ans=-1;
		while(l<=r)
		{
			int mid=(l+r)>>1;
			if(Check(mid))
				ans=mid,l=mid+1;
			else
				r=mid-1;
		}
		printf("%d\n",ans+1);
	}
	return 0;
}