#1407 : 后缀数组二·重复旋律2
Time Limit:5000ms
Case Time Limit:1000ms
Memory Limit:256MB
描述
小Hi平时的一大兴趣爱好就是演奏钢琴。我们知道一个音乐旋律被表示为长度为 N 的数构成的数列。小Hi在练习过很多曲子以后发现很多作品自身包含一样的旋律。
旋律可以表示为一段连续的数列，相似的旋律在原数列不可重叠，比如在1 2 3 2 3 2 1 中 2 3 2 出现了一次，2 3 出现了两次，小Hi想知道一段旋律中出现次数至少为两次的旋律最长是多少？
输入
第一行一个整数 N。1≤N≤100000
接下来有 N 个整数，表示每个音的数字。1≤数字≤1000
输出
一行一个整数，表示答案。
- Sample Input
-
8
1 2 3 2 3 2 3 1 - Sample Output
- 2
分析：
和POJ1743是一样的...只不过是二分判定的时候>=和>的问题...
代码：
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
//by NeighThorn
using namespace std; const int maxn=100000+5; int n,s[maxn],gs[maxn],sa[maxn],wv[maxn],wb[maxn],ran[maxn],height[maxn]; inline bool cmp(int *x,int a,int b,int l){
return x[a]==x[b]&&x[a+l]==x[b+l];
} inline void da(int *sa,int *x,int n,int m){
int i,j,p,*y=wb;
for(i=0;i<m;i++) gs[i]=0;
for(i=0;i<n;i++) gs[x[i]]++;
for(i=1;i<m;i++) gs[i]+=gs[i-1];
for(i=n-1;~i;i--) sa[--gs[x[i]]]=i;
for(j=1,p=1;p<n;j<<=1,m=p){
for(i=n-j,p=0;i<n;i++) y[p++]=i;
for(i=0;i<n;i++) if(sa[i]>=j) y[p++]=sa[i]-j;
for(i=0;i<n;i++) wv[i]=x[y[i]];
for(i=0;i<m;i++) gs[i]=0;
for(i=0;i<n;i++) gs[wv[i]]++;
for(i=1;i<m;i++) gs[i]+=gs[i-1];
for(i=n-1;~i;i--) sa[--gs[wv[i]]]=y[i];
p=1;swap(x,y);x[sa[0]]=0;
for(i=1;i<n;i++) x[sa[i]]=cmp(y,sa[i],sa[i-1],j)?p-1:p++;
}
} inline void calheight(int n){
int i,j,k=0;
for(i=0;i<=n;i++) ran[sa[i]]=i;
for(i=0;i<n;height[ran[i++]]=k)
for(k?k--:233,j=sa[ran[i]-1];s[i+k]==s[j+k];k++);
} inline bool check(int x){
int Min=n,Max=0;bool ans=0;
for(int i=1;i<=n;i++){
if(height[i]<x){
if(Max!=0)
if(Max-Min>=x)
ans=1;
Min=Max=sa[i];
continue;
}
Min=min(Min,sa[i]),Max=max(Max,sa[i]);
}
if(Max!=0&&Max-Min>=x)
ans=1;
return ans;
} signed main(void){
scanf("%d",&n);
for(int i=0;i<n;i++)
scanf("%d",&s[i]),ran[i]=s[i];
da(sa,ran,n+1,1001);calheight(n);
int l=1,r=n>>1,ans=0;
while(l<=r){
int mid=(l+r)>>1;
if(check(mid))
ans=mid,l=mid+1;
else
r=mid-1;
}
printf("%d\n",ans);
return 0;
}//Cap ou pas cap. Pas cap.
By NeighThorn