题目大意
直接用了hzwer的题意
题意：有N(1 <= N <=20000)个音符的序列来表示一首乐曲，每个音符都是1..88范围内的整数，现在要找一个重复的主题。“主题”是整个音符序列的一个子串，它需要满足如下条件：
1.长度至少为5个音符。
2.在乐曲中重复出现。(可能经过转调，“转调”的意思是主题序列中每个音符都被加上或减去了同一个整数值)
3.重复出现的同一主题不能有公共部分。
分析
对于区间加一个数也算相同
转化一下就变成相邻两数差相同
变成问重复两次的不相交的子串最长是多少
做法1
sa，二分+判断，记录组内最大最小值就好
做法2
sam，搞出后缀树
一个节点(x)长度可以是([1..max(x)])
用(max(x))和(x)的right集中最大减最小比一下取min就好
注意
答案小于5输出0
转化问题后不相交变成了两个子串中间至少一个间隔
姿势
以后后缀自动机/后缀树 用这些变量名
int last,tot;
int ch[M][N];
int stp[M];
int fa[M];
int right[M];
int hg[M],tg;
struct suftree{
int y,nxt;
}go[M];
last和tot在main里初始化
多组数据注意初始化last,tot,ch,right
solution
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cctype>
#include <cmath>
using namespace std;
const int N=180;
const int M=40007;
const int INF=0x3f3f3f3f;
inline int rd(){
int x=0;bool f=1;char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=0;
for(;isdigit(c);c=getchar()) x=x*10+c-48;
return f?x:-x;
}
int n;
int a[M];
int ans;
int last,tot;
int ch[M][N];
int stp[M];
int fa[M];
int right[M];
int mx[M],mn[M];
int hg[M],tg;
struct suftree{
int y,nxt;
}go[M];
int newnode(int ss){
stp[++tot]=ss;
return tot;
}
int ext(int p,int q,int d){
int nq=newnode(stp[p]+1);
fa[nq]=fa[q];
fa[q]=nq;
memcpy(ch[nq],ch[q],sizeof(ch[q]));
for(;p&&ch[p][d]==q;p=fa[p]) ch[p][d]=nq;
return nq;
}
int sam(int p,int d){
int np=ch[p][d];
if(np) return (stp[p]+1==stp[np]) ? np : ext(p,np,d);
np=newnode(stp[p]+1);
for(;p&&!ch[p][d];p=fa[p]) ch[p][d]=np;
if(!p) fa[np]=1;
else{
int q=ch[p][d];
fa[np]= (stp[p]+1==stp[q]) ? q : ext(p,q,d);
}
return np;
}
void addgo(int x,int y){
go[++tg].y=y; go[tg].nxt=hg[x]; hg[x]=tg;
}
void dfs(int x){
int p,y;
if(!right[x]) mx[x]=0, mn[x]=INF;
else mx[x]=mn[x]=right[x];
for(p=hg[x];p;p=go[p].nxt){
y=go[p].y;
dfs(y);
mx[x]=max(mx[x],mx[y]);
mn[x]=min(mn[x],mn[y]);
}
ans=max(ans,min(stp[x],mx[x]-mn[x]-1));
}
int main(){
int i;
while((n=rd())!=0){
memset(right,0,sizeof(right));
memset(ch,0,sizeof(ch));
last=tot=1;
for(i=1;i<=n;i++) a[i]=rd();
for(i=1;i<n;i++) a[i]=a[i+1]-a[i];
n--;
for(i=1;i<=n;i++){
last=sam(last,a[i]+88);
right[last]=i;
}
memset(hg,0,sizeof(hg)); tg=0;
for(i=2;i<=tot;i++) addgo(fa[i],i);
ans=0;
dfs(1);
ans++;
if(ans<5) puts("0");
else printf("%d
",ans);
}
return 0;
}