https://blog.csdn.net/WAautomaton/article/details/85057257
解法一：后缀数组
显然将原数组差分后答案就是所有不相交不相邻重复子串个数+n*(n-1)/2。
答案=重复子串个数-相邻或相交重复子串个数。
前者单调栈直接求解，注意细节，重点在后者。
由于是有关相交的计数问题，考虑类似[NOI2016]优秀的拆分的设关键点的做法。
枚举两个串的偏移量k，每k个位置设一个关键点，我们需要保证任意两个相距为k的重复子串都在且仅在它们覆盖的第一个关键点处被计算一次。
求出每相邻两个关键点的LCP和LCS，发现答案是一个等差数列，注意式子的推导，不能重复计算。
#include<cstdio>
#include<cstring>
#include<algorithm>
#define rep(i,l,r) for (int i=(l); i<=(r); i++)
typedef long long ll;
using namespace std; const int N=;
int n,tot,top,s[N],b[N],stk[N],lg[N];
ll res,sm; struct SA{
int s[N],c[N],x[N],y[N],sa[N],rk[N],st[N][],h[N];
bool Cmp(int a,int b,int l){ return a+l<=n && b+l<=n && y[a]==y[b] && y[a+l]==y[b+l]; } void build(int m){
memset(y,,sizeof(y));
rep(i,,m) c[i]=;
rep(i,,n) c[x[i]=s[i]]++;
rep(i,,m) c[i]+=c[i-];
for (int i=n; i; i--) sa[c[x[i]]--]=i;
for (int k=,p=; p<n; k<<=,m=p){
p=;
rep(i,n-k+,n) y[++p]=i;
rep(i,,n) if (sa[i]>k) y[++p]=sa[i]-k;
rep(i,,m) c[i]=;
rep(i,,n) c[x[y[i]]]++;
rep(i,,m) c[i]+=c[i-];
for (int i=n; i; i--) sa[c[x[y[i]]]--]=y[i];
rep(i,,n) y[i]=x[i]; x[sa[p=]]=;
rep(i,,n) x[sa[i]]=Cmp(sa[i-],sa[i],k) ? p : ++p;
}
} void height(){
int k=;
rep(i,,n) rk[sa[i]]=i;
rep(i,,n){
for (int j=sa[rk[i]-]; i+k<=n && j+k<=n && s[i+k]==s[j+k]; k++);
h[rk[i]]=k; if (k) k--;
}
rep(i,,n) st[i][]=h[i];
rep(j,,lg[n]) rep(i,,n-(<<j)+) st[i][j]=min(st[i][j-],st[i+(<<(j-))][j-]);
} int que(int a,int b){
int x=rk[a],y=rk[b];
if (x==y) return n-a+;
if (x>y) swap(x,y);
x++; int t=lg[y-x+];
return min(st[x][t],st[y-(<<t)+][t]);
}
}sa1,sa2; int LCP(int l,int r){ return sa1.que(l,r); }
int LCS(int l,int r){ return sa2.que(n-r+,n-l+); } int main(){
freopen("P5161.in","r",stdin);
freopen("P5161.out","w",stdout);
scanf("%d",&n);
rep(i,,n) lg[i]=lg[i>>]+;
rep(i,,n) scanf("%d",&s[i]);
n--; rep(i,,n) b[i]=s[i]=s[i+]-s[i];
sort(b+,b+n+); tot=unique(b+,b+n+)-b-;
rep(i,,n) s[i]=lower_bound(b+,b+tot+,s[i])-b;
rep(i,,n) sa1.s[i]=sa2.s[n-i+]=s[i];
sa1.build(tot); sa2.build(tot); sa1.height(); sa2.height();
rep(i,,n+){
res+=sm;
for (; top && sa1.h[stk[top]]>=sa1.h[i]; top--)
sm-=1ll*(sa1.h[stk[top]]-sa1.h[i])*(stk[top]-stk[top-]);
sm+=sa1.h[stk[++top]=i];
}
rep(i,,n){
for (int j=i; j+i<=n; j+=i){
int a=min(i,LCS(j,j+i)),b=LCP(j,j+i),l=min(a-,b+a-i);
if (l>=) res-=1ll*(l+)*(b+a-i)-1ll*l*(l+)/;
}
}
printf("%lld\n",res+1ll*n*(n+)/);
return ;
}
解法二：后缀自动机+线段树合并
建出parent树，注意到任意两个位置的LCP就是它们在parent树上LCA的mx。于是每个结点上用一棵线段树维护相关信息，同时用一个vector记录子树中的点。线段树的合并直接用普通线段树合并，vector的合并用启发式合并。
复杂度$O(n\log^2 n)$，但由于常数小所以不会被卡。（当然用时是解法一的三倍）
#include<map>
#include<cstdio>
#include<vector>
#include<algorithm>
#define lson ls[x],L,mid
#define rson rs[x],mid+1,R
#define rep(i,l,r) for (int i=(l); i<=(r); i++)
#define For(i,u) for (int i=h[u]; i; i=nxt[i])
typedef long long ll;
using namespace std; const int N=,M=;
ll ans,v[M],vs[M];
int n,p,np,lst=,nd=,nd2,cnt,a[N],pos[N],rt[N],mx[N];
int fa[N],ls[M],rs[M],to[N<<],nxt[N<<],h[N];
map<int,int>son[N];
vector<int>ve[N],*f[N];
void add(int u,int v){ to[++cnt]=v; nxt[cnt]=h[u]; h[u]=cnt; } void ext(int c,int x){
p=lst; lst=np=++nd; mx[np]=mx[p]+; pos[x]=np;
while (p && !son[p][c]) son[p][c]=np,p=fa[p];
if (!p) fa[np]=;
else{
int q=son[p][c];
if (mx[q]==mx[p]+) fa[np]=q;
else{
int nq=++nd; mx[nq]=mx[p]+;
son[nq]=son[q]; fa[nq]=fa[q]; fa[q]=fa[np]=nq;
while (p && son[p][c]==q) son[p][c]=nq,p=fa[p];
}
}
} void mdf(int &x,int L,int R,int k){
if (!x) x=++nd2;
v[x]++; vs[x]+=k;
if (L==R) return;
int mid=(L+R)>>;
if (k<=mid) mdf(lson,k); else mdf(rson,k);
} ll que(int x,int L,int R,int l,int r,int k){
l=max(l,L); r=min(r,R);
if(!x || l>r || r< || l>n) return ;
if (L==l && r==R) return k ? vs[x] : v[x];
int mid=(L+R)>>;
if (r<=mid) return que(lson,l,r,k);
else if (l>mid) return que(rson,l,r,k);
else return que(lson,l,mid,k)+que(rson,mid+,r,k);
} int merge(int x,int y){
if (!x || !y) return x|y;
v[x]+=v[y]; vs[x]+=vs[y];
ls[x]=merge(ls[x],ls[y]);
rs[x]=merge(rs[x],rs[y]);
return x;
} void dfs(int u){
int k=mx[u];
For(i,u){
int v=to[i]; dfs(v);
if (f[u]->size()<f[v]->size()) swap(f[u],f[v]),swap(rt[u],rt[v]);
int ed=f[v]->size()-;
rep(j,,ed){
int x=f[v]->at(j);
ll A=que(rt[u],,n,x-k-,x-,)*(x-)-que(rt[u],,n,x-k-,x-,)+que(rt[u],,n,,x-k-,)*k;
ll B=que(rt[u],,n,x+,x+k+,)-que(rt[u],,n,x+,x+k+,)*(x+)+que(rt[u],,n,x+k+,n,)*k;
ans+=A+B;
}
rep(j,,ed) f[u]->push_back(f[v]->at(j));
rt[u]=merge(rt[u],rt[v]);
}
} int main(){
freopen("P5161.in","r",stdin);
freopen("P5161.out","w",stdout);
scanf("%d",&n);
rep(i,,n) scanf("%d",&a[i]);
n--; rep(i,,n) a[i]=a[i+]-a[i];
ans=1ll*n*(n+)>>;
rep(i,,n) ext(a[i],i);
rep(i,,nd) add(fa[i],i);
rep(i,,nd) f[i]=&ve[i];
rep(i,,n) f[pos[i]]->push_back(i),mdf(rt[pos[i]],,n,i);
dfs(); printf("%lld\n",ans);
return ;
}