(O(n^4)) 的暴力就是枚举两个子串是不是能满足关系
然后 (dp) 最长链，显然这东西是铁废物
在 (SAM) 上那么转移必然是从父亲向儿子进行的
那么问题就变成了如何维护出现两次的限制
本质上出现了两次就是说这个子串的 (endpos) 有至少两个点在上一个子串的所在区间 ([st,ed]) 中出现了
（还是不熟练，想到这个用了好久）
线段树合并求 (endpos) 是 (trivial)
那么可以得到一个 (O((2n)^2log n)) 的做法
当然可以用一些优化卡过 (n=4000) 的点
如何进行快速完整的转移
其实本质上可以在后缀树上倍增，每次暴力跳来找到最大的满足条件的祖先，然后转移即可
貌似可以证明深度更深的点的答案不会劣于深度浅的点
不过倍增复杂度不行，那么考虑记录转移点即可
#include<bits/stdc++.h>
using namespace std;
#define reg register
namespace yspm{
inline int read(){
int res=0,f=1; char k;
while(!isdigit(k=getchar())) if(k=='-') f=-1;
while(isdigit(k)) res=res*10+k-'0',k=getchar();
return res*f;
}
const int N=4e5+10,M=N*40;
char s[N];
int son[N][26],n,rt[N],fa[N],len[N],tot=1,las=1,ls[M],rs[M],sum[M],num;
inline void push_up(int x){return sum[x]=sum[ls[x]]+sum[rs[x]],void();}
inline void upd(int &p,int l,int r,int pos){
if(!p) p=++num; if(l==r) return sum[p]=1,void();
int mid=(l+r)>>1; if(pos<=mid) upd(ls[p],l,mid,pos); else upd(rs[p],mid+1,r,pos);
return push_up(p);
}
inline int merge(int x,int y,int l,int r){
if(!x||!y) return x+y; if(l==r) return sum[x]|=sum[y],x;
int p=++num,mid=(l+r)>>1;
ls[p]=merge(ls[x],ls[y],l,mid); rs[p]=merge(rs[x],rs[y],mid+1,r);
return push_up(p),p;
}
struct node{int to,nxt;}e[N<<1];
int head[N],cnt,f[N],ans,fir[N];
inline void add(int u,int v){return e[++cnt].to=v,e[cnt].nxt=head[u],head[u]=cnt,void();}
inline void extend(int x,int pos){
int tmp=las,np=las=++tot; len[np]=len[tmp]+1; upd(rt[np],1,n,pos);
while(!son[tmp][x]&&tmp) son[tmp][x]=np,tmp=fa[tmp];
if(!tmp) return fa[np]=1,void();
int q=son[tmp][x]; if(len[q]==len[tmp]+1) return fa[np]=q,void();
int clone=++tot; for(reg int i=0;i<26;++i) son[clone][i]=son[q][i];
len[clone]=len[tmp]+1; fa[clone]=fa[q]; fa[q]=fa[np]=clone;
while(son[tmp][x]==q) son[tmp][x]=clone,tmp=fa[tmp];
return ;
}
inline void getpos(int x){
fir[x]=len[x];
for(reg int i=head[x];i;i=e[i].nxt) getpos(e[i].to),rt[x]=merge(rt[x],rt[e[i].to],1,n),fir[x]=max(fir[x],fir[e[i].to]);
return ;
}
inline int find(int p,int l,int r){
if(l==r) return l;
int mid=(l+r)>>1;
if(sum[ls[p]]) return find(ls[p],l,mid);
else return find(rs[p],mid+1,r);
}
inline int query(int p,int l,int r,int st,int ed){
if(!p) return 0; if(l==r) return sum[p];
int mid=(l+r)>>1,res=0;
if(st<=mid) res+=query(ls[p],l,mid,st,ed);
if(res>=2) return res;
if(ed>mid) res+=query(rs[p],mid+1,r,st,ed);
return res;
}
int d[N];
inline void dfs(int x){
if(x==1) f[x]=0,d[x]=1;
else{
if(query(rt[d[fa[x]]],1,n,fir[x]-len[x]+len[d[fa[x]]],fir[x])>=2) f[x]=f[fa[x]]+1,d[x]=x;
else f[x]=f[fa[x]],d[x]=d[fa[x]];
ans=max(ans,f[x]);
}for(reg int i=head[x];i;i=e[i].nxt) dfs(e[i].to); return ;
}
signed main(){
scanf("%s",s+1); n=strlen(s+1);
for(reg int i=1;i<=n;++i) extend(s[i]-'a',i);
for(reg int i=2;i<=tot;++i) add(fa[i],i);
getpos(1);
dfs(1); printf("%d
",ans);
return 0;
}
}
signed main(){return yspm::main();}
最后记录一个卡常实况
当我直接 (query o ls) 之后判 (resge 2) 然后返回，快了 (+inf) 倍