题目链接
题解：首先，由于可以变调，我们把字符串每个字符变成相邻两个字符的差。然后跑后缀自动机，得到sa，rnk和height。二分答案k，k表示原字符串的某个不重复公共子串的长度，就变成了判定问题。把所有排名相邻且height>=k-1的字符串分为一组，然后如果这组中sa的最大值和sa的最小值的差>=k，原串中就可以找到满足条件的2个长度为k的字符串。感性的证明：长得像的后缀都排到了一起！（捂脸）
代码：
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=20005;
int m,n,a[N],c[N],t1[N],t2[N],sa[N],rnk[N],h[N];
bool cmp(int *y,int p,int q,int k){
int a=p+k>=n?-1:y[p+k];
int b=q+k>=n?-1:y[q+k];
return y[p]==y[q]&&a==b;
}
void build_sa(int m){
int *x=t1,*y=t2;
for(int i=0;i<m;i++){
c[i]=0;
}
for(int i=0;i<n;i++){
c[x[i]=a[i]]++;
}
for(int i=1;i<m;i++){
c[i]+=c[i-1];
}
for(int i=n-1;i>=0;i--){
sa[--c[x[i]]]=i;
}
for(int k=1;k<=n;k<<=1){
int p=0;
for(int i=n-k;i<n;i++){
y[p++]=i;
}
for(int i=0;i<n;i++){
if(sa[i]>=k){
y[p++]=sa[i]-k;
}
}
for(int i=0;i<m;i++){
c[i]=0;
}
for(int i=0;i<n;i++){
c[x[y[i]]]++;
}
for(int i=1;i<m;i++){
c[i]+=c[i-1];
}
for(int i=n-1;i>=0;i--){
sa[--c[x[y[i]]]]=y[i];
}
swap(x,y);
p=1;
x[sa[0]]=0;
for(int i=1;i<n;i++){
x[sa[i]]=cmp(y,sa[i-1],sa[i],k)?p-1:p++;
}
if(p>=n){
break;
}
m=p;
}
for(int i=0;i<n;i++){
rnk[sa[i]]=i;
}
for(int i=0,j,k=0;i<n;i++){
if(k){
k--;
}
if(!rnk[i]){
continue;
}
j=sa[rnk[i]-1];
while(a[i+k]==a[j+k]){
k++;
}
h[rnk[i]]=k;
}
}
bool check(int k){
int maxn=sa[0],minn=sa[0];
for(int i=1;i<n;i++){
if(h[i]>=k-1){
maxn=max(maxn,sa[i]);
minn=min(minn,sa[i]);
}else{
maxn=minn=sa[i];
}
if(maxn-minn>=k){
return true;
}
}
return false;
}
int main(){
while(scanf("%d",&m)&&m){
n=m-1;
for(int i=0;i<m;i++){
scanf("%d",&a[i]);
}
for(int i=0;i<n;i++){
a[i]=a[i]-a[i+1]+88;
}
build_sa(200);
int l=0,r=m/2;
while(l<r){
int mid=(l+r+1)/2;
if(check(mid)){
l=mid;
}else{
r=mid-1;
}
}
printf("%d
",l<5?0:l);
}
return 0;
}