(Description)
给定一段数字序列(Ai∈[1,88])，求最长的两个子序列满足：
1.长度至少为5
2.一个子序列可以通过全部加或减同一个数来变成另一个子序列
3.两个子序列没有重叠部分
(Solution)
求不重叠最长重复子序列：
SA：
首先二分k，判断是否存在长度为k的不重叠的相同子序列
把排序后的后缀按ht分组，每组中后缀的ht>=k，这样满足相同序列长度至少为k的两个后缀一定在同一组中(且同一组中任意两个都满足)
然后在每组中判断是否有max{sa[]}-min{sa[]}>=k，这样可以满足没有重叠部分。若有一组满足，则存在。
SAM：
一个节点出现位置终点的集合(right)为其所有儿子节点right集合的并。而且这个点所代表的串一定在其子节点代表的串中出现过。
于是从底向上更新，我们可以得到每个点代表的串中 位置最靠左的右端点L和最靠右的右端点R。
如果R[i]-L[i]>=len[i]，说明这个点代表的最长串重复出现且不重叠，可以用len[i]更新ans。实际上min(R[i]-L[i],len[i])即为每个点合法的答案。（后者写不写都对啊。。是因为最终答案的关系？）
清空son[]、tm[]！
对于要求2，其实可以看做两个子序列相邻两项差值都相等，如1,2,4,6与4,5,7,9，相邻两项差值的序列都为1,2,2，那么可以满足条件
原序列转化为差值序列，长度最后时要+1
SA：
//860K 125MS
#include <cstdio>
#include <cctype>
#include <algorithm>
#define gc() getchar()
const int N=2e4+5,MAX=88;
int n,sa[N],ht[N],rk[N],sa2[N],A[N],tm[N];
inline int read()
{
int now=0;register char c=gc();
for(;!isdigit(c);c=gc());
for(;isdigit(c);now=now*10+c-'0',c=gc());
return now;
}
void Get_SA()
{
int *x=rk,*y=sa2,m=200;
for(int i=0; i<=m; ++i) tm[i]=0;
for(int i=1; i<=n; ++i) ++tm[x[i]=A[i]];
for(int i=1; i<=m; ++i) tm[i]+=tm[i-1];
for(int i=n; i; --i) sa[tm[x[i]]--]=i;
for(int p=0,k=1; k<n; k<<=1,m=p,p=0)
{
for(int i=n-k+1; i<=n; ++i) y[++p]=i;
for(int i=1; i<=n; ++i) if(sa[i]>k) y[++p]=sa[i]-k;
for(int i=0; i<=m; ++i) tm[i]=0;
for(int i=1; i<=n; ++i) ++tm[x[i]];
for(int i=1; i<=m; ++i) tm[i]+=tm[i-1];
for(int i=n; i; --i) sa[tm[x[y[i]]]--]=y[i];
std::swap(x,y), p=x[sa[1]]=1;
for(int i=2; i<=n; ++i)
x[sa[i]]=y[sa[i-1]]==y[sa[i]]&&y[sa[i-1]+k]==y[sa[i]+k]?p:++p;
if(p>=n) break;
}
}
void Get_ht()
{
for(int i=1; i<=n; ++i) rk[sa[i]]=i;
ht[1]=0;
for(int k=0,p,i=1; i<=n; ++i)
{
if(rk[i]==1) continue;
if(k) --k;
p=sa[rk[i]-1];
while(i+k<=n&&p+k<=n&&A[i+k]==A[p+k]) ++k;
ht[rk[i]]=k;
}
}
bool Check(int k)
{
int mx=sa[1],mn=sa[1];
for(int i=2; i<=n; ++i)
if(ht[i]>=k) mx=std::max(mx,sa[i]),mn=std::min(mn,sa[i]);
else if(mx-mn>=k) return 1;
else mn=mx=sa[i];
return mx-mn>=k;
}
int Solve()
{
// for(int i=1; i<=n; ++i) printf("%d ",sa[i]);
int l=4,r=n,mid,res=-1;
while(l<r)
if(Check(mid=l+r>>1)) res=mid,l=mid+1;
else r=mid;
return res+1;
}
int main()
{
while(n=read(),n)
{
for(int i=1; i<=n; ++i) A[i]=read();
--n;
for(int i=1; i<=n; ++i) A[i]=A[i+1]-A[i]+MAX;
Get_SA(), Get_ht();
printf("%d
",Solve());
}
return 0;
}
SAM：
//29504K 594MS
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
#define gc() getchar()
const int N=4e4+5,MAX=88;
inline int read()
{
int now=0;register char c=gc();
for(;!isdigit(c);c=gc());
for(;isdigit(c);now=now*10+c-'0',c=gc());
return now;
}
struct Suffix_Automaton
{
int n,a[N],tot,las,fa[N],son[N][180],len[N],L[N],R[N],tm[N],A[N];
void Insert(int c)
{
int np=++tot,p=las; len[las=np]=len[p]+1;
for(; p&&!son[p][c]; p=fa[p]) son[p][c]=np;
if(!p) fa[np]=1;
else
{
int q=son[p][c];
if(len[q]==len[p]+1) fa[np]=q;
else
{
int nq=++tot; len[nq]=len[p]+1;
memcpy(son[nq],son[q],sizeof son[q]);
fa[nq]=fa[q], fa[q]=fa[np]=nq;
for(; son[p][c]==q; p=fa[p]) son[p][c]=nq;
}
}
}
void Build()
{
memset(tm,0,sizeof tm), memset(son,0,sizeof son);//!!!
for(int i=1; i<=n; ++i) a[i]=read();
--n;
for(int i=1; i<=n; ++i) a[i]=a[i+1]-a[i]+MAX;
tot=las=1, len[1]=0;
for(int i=1; i<=n; ++i) Insert(a[i]);
for(int i=1; i<=tot; ++i) ++tm[len[i]];
for(int i=1; i<=n; ++i) tm[i]+=tm[i-1];
for(int i=1; i<=tot; ++i) A[tm[len[i]]--]=i;
}
void Query()
{
memset(R,0,sizeof R), memset(L,0x3f,sizeof L);
for(int i=1,p=1; i<=n; ++i)
p=son[p][a[i]], L[p]=R[p]=i;//a[]与A[]。。。
for(int i=tot,x=A[i]; i; x=A[--i])
L[fa[x]]=std::min(L[fa[x]],L[x]), R[fa[x]]=std::max(R[fa[x]],R[x]);
int ans=0;
for(int i=1; i<=tot; ++i)
ans=std::max(ans,std::min(R[i]-L[i],len[i]));
printf("%d
",ans<4?0:ans+1);
}
}sam;
int main()
{
while(sam.n=read(),sam.n) sam.Build(), sam.Query();
return 0;
}