分析
后缀数组算法里的height数组每个区间的最小值都对应着原串的两个后缀的LCP。神奇的性质。
代码
// 自己撸的SA常数还是很大
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn=100050;
int a[maxn],n,d[maxn];
namespace suffixArray {
int sa[maxn],x[maxn],c[maxn],t[maxn];
bool cmp(int u,int v,int l) {
return x[u]==x[v]&&(u+l>n?0:x[u+l])==(v+l>n?0:x[v+l]);
}
void da() {
--n;
int m=200;
for(int i = 0; i <= m; ++i) c[i]=0;
for(int i = 1; i <= n; ++i) c[x[i]=d[i+1]+100]++;
for(int i = 1; i <= m; ++i) c[i]+=c[i-1];
for(int i = n; i >= 1; --i) sa[c[x[i]]--]=i;
for(int l = 1; l <= n; l<<=1) {
int cnt=0;
for(int i = n-l+1; i <= n; ++i) t[++cnt]=i;
for(int i = 1; i <= n; ++i) {
if(sa[i]>l) t[++cnt]=sa[i]-l;
}
for(int i = 0; i <= m; ++i) c[i]=0;
for(int i = 1; i <= n; ++i) c[x[i]]++;
for(int i = 0; i <= m; ++i) c[i]+=c[i-1];
for(int i = n; i >= 1; --i) sa[c[x[t[i]]]--]=t[i];
m=0,t[sa[1]]=++m;
for(int i = 2; i <= n; ++i) {
if(cmp(sa[i],sa[i-1],l)) t[sa[i]]=m;
else t[sa[i]]=++m;
}
swap(x,t);
if(m==n) break;
}
}
int height[maxn],*rank=x;
void calHeight() {
int h=0,*D=d+1;
for(int i = 1; i <= n; ++i) {
if(h) --h;
while(D[i+h]==D[sa[rank[i]-1]+h]) ++h;
height[rank[i]]=h;
}
}
}
bool check(int x) {
int M=0,m=1e9;
using suffixArray::sa;
using suffixArray::height;
for(int i = 2; i <= n; ++i) {
if(height[i]<x) M=m=sa[i];
else {
M=max(M,sa[i]);
m=min(m,sa[i]);
if(M-m>x) return true;
}
}
return false;
}
int main() {
while(~scanf("%d", &n)&&n) {
for(int i = 1; i <= n; ++i) scanf("%d", a+i),d[i]=a[i]-a[i-1];
suffixArray::da();
suffixArray::calHeight();
int ans=0,l=0,r=n;
while(l<=r) {
int mid=(l+r)>>1;
if(check(mid)) ans=mid,l=mid+1;
else r=mid-1;
}
ans++;
if(ans<5) ans=0;
printf("%d
", ans);
}
return 0;
}
刚好卡过的ST表+单调栈做法
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn=100050;
int a[maxn],n,d[maxn];
namespace suffixArray{
int sa[maxn],x[maxn],c[maxn],t[maxn];
bool cmp(int u,int v,int l) {
return x[u]==x[v]&&(u+l>n?0:x[u+l])==(v+l>n?0:x[v+l]);
}
bool cmp2(int u,int v) {
return x[u]<x[v];
}
void da() {
--n;
for(int i = 1; i <= n; ++i) {
x[i]=d[i+1];
sa[i]=i;
}
sort(sa+1,sa+1+n,cmp2);
int m=0;
t[sa[1]]=++m;
for(int i = 2; i <= n; ++i) {
if(x[sa[i]]==x[sa[i-1]]) t[sa[i]]=m;
else t[sa[i]]=++m;
}
swap(x,t);
for(int l = 1; l <= n; l<<=1) {
int cnt=0;
for(int i = n-l+1; i <= n; ++i) t[++cnt]=i;
for(int i = 1; i <= n; ++i) {
if(sa[i]>l) t[++cnt]=sa[i]-l;
}
for(int i = 0; i <= m; ++i) c[i]=0;
for(int i = 1; i <= n; ++i) c[x[i]]++;
for(int i = 0; i <= m; ++i) c[i]+=c[i-1];
for(int i = n; i >= 1; --i) sa[c[x[t[i]]]--]=t[i];
m=0,t[sa[1]]=++m;
for(int i = 2; i <= n; ++i) {
if(cmp(sa[i],sa[i-1],l)) t[sa[i]]=m;
else t[sa[i]]=++m;
}
swap(x,t);
if(m==n) break;
}
}
int height[maxn],*rank=x;
void calHeight() {
int h=0,*D=d+1;
for(int i = 1; i <= n; ++i) {
if(h) --h;
while(D[i+h]==D[sa[rank[i]-1]+h]) ++h;
height[rank[i]]=h;
}
}
}
int L[maxn],R[maxn];
namespace getLR {
int q[maxn],top;
using suffixArray::height;
void solo() {
top=0;
for(int i = 2; i <= n; ++i) {
while(top&&height[q[top]]>=height[i]) --top;
if(top) L[i]=q[top]+1;
else L[i]=2;
q[++top]=i;
}
top=0;
for(int i = n; i >= 2; --i) {
while(top&&height[q[top]]>=height[i]) --top;
if(top) R[i]=q[top]-1;
else R[i]=n;
q[++top]=i;
}
}
}
namespace ST {
using suffixArray::sa;
int m[maxn][20],M[maxn][20],Log2[maxn];
void init() {
if(!Log2[2]) {
Log2[2]=1;
for(int i = 3; i < maxn; ++i) {
Log2[i]=Log2[i>>1]+1;
}
}
for(int j = 0; (1<<j) <= n; ++j) {
for(int i = 1; i+(1<<j)-1 <= n; ++i) {
if(j==0) m[i][j]=M[i][j]=sa[i];
else {
int x=i+(1<<(j-1));
m[i][j]=min(m[i][j-1],m[x][j-1]);
M[i][j]=max(M[i][j-1],M[x][j-1]);
}
}
}
}
int dis(int x,int y) {
if(x>y) swap(x,y);
int k=Log2[y-x+1];
return max(M[x][k],M[y-(1<<k)+1][k])-min(m[x][k],m[y-(1<<k)+1][k]);
}
}
void deb(int *arr) {
for(int i = 1; i <= n; ++i) {
cout<<arr[i]<<" ";
}
cout<<endl;
}
int main() {
while(~scanf("%d", &n)&&n) {
for(int i = 1; i <= n; ++i) scanf("%d", a+i),d[i]=a[i]-a[i-1];
suffixArray::da();
suffixArray::calHeight();
ST::init();
getLR::solo();
int ans=0;
for(int i = 2; i <= n; ++i) {
int t=min(suffixArray::height[i],ST::dis(L[i]-1,R[i])-1);
ans=max(ans,t);
}
ans++;
if(ans<5) ans=0;
printf("%d
", ans);
}
return 0;
}