解法:先建出samsamsam,显然只有当sizep=1size_p=1sizep=1的时候才对答案有贡献。
于是对于每个sizep=1size_p=1sizep=1的状态分情况更新答案。- pos=[pos[p]−len[link[p]]+1,pos[p]]pos=[pos[p]-len[link[p]]+1,pos[p]]pos=[pos[p]−len[link[p]]+1,pos[p]],那么ansi=min{ansi,lenlinkp+1}ans_i=min\{ans_i,len_{link_p}+1\}ansi=min{ ansi,lenlinkp+1}
- pos=[pos[p]−len[p]+1,pos[p]−len[link[p]]]pos=[pos[p]-len[p]+1,pos[p]-len[link[p]]]pos=[pos[p]−len[p]+1,pos[p]−len[link[p]]],那么ansi=min{ansi,lenp−i+1}ans_i=min\{ans_i,len_p-i+1\}ansi=min{ ansi,lenp−i+1}
第一类直接上线段树。
第二类?我们令fi=ansi+if_i=ans_i+ifi=ansi+i,用线段树维护fif_ifi的值最后统计答案的时候减去iii即可。 代码:#include#define ri register int#define lc (p<<1)#define rc (p<<1|1)#define mid (l+r>>1)using namespace std;inline int read(){ int ans=0; char ch=getchar(); while(!isdigit(ch))ch=getchar(); while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar(); return ans; }const int N=9e5+5;int n,ans[500005];char s[N];struct SGT{ int mn[N<<1]; inline void build(int p,int l,int r,int f){ mn[p]=0x3f3f3f3f; if(l==r){ mn[p]=f?n+l:n;return;} build(lc,l,mid,f),build(rc,mid+1,r,f); } inline void update(int p,int l,int r,int ql,int qr,int v){ if(ql>r||qr mid)update(rc,mid+1,r,ql,qr,v); else update(lc,l,mid,ql,mid,v),update(rc,mid+1,r,mid+1,qr,v); } inline void query(int p,int l,int r,int f){ if(l==r){ ans[l]=min(ans[l],mn[p]-f*l);return;} mn[lc]=min(mn[lc],mn[p]),query(lc,l,mid,f); mn[rc]=min(mn[rc],mn[p]),query(rc,mid+1,r,f); }}T1,T2;struct SAM{ int last,tot,len[N],link[N],son[N][26],siz[N],rk[N],cnt[500005],pos[N]; SAM(){ last=tot=1,len[0]=-1;} inline void expand(int x,int id){ int p=last,np=++tot; siz[last=np]=1,pos[np]=id,len[np]=len[p]+1; while(p&&!son[p][x])son[p][x]=np,p=link[p]; if(!p){ link[np]=1;return;} int q=son[p][x],nq; if(len[q]==len[p]+1){ link[np]=q;return;} len[nq=++tot]=len[p]+1,memcpy(son[nq],son[q],sizeof(son[q])),link[nq]=link[q],link[q]=link[np]=nq; while(p&&son[p][x]==q)son[p][x]=nq,p=link[p]; } inline void solve(){ for(ri i=1;i<=tot;++i)++cnt[len[i]]; for(ri i=1;i<=n;++i)cnt[i]+=cnt[i-1]; for(ri i=1;i<=tot;++i)rk[cnt[len[i]]--]=i; T1.build(1,1,n,0),T2.build(1,1,n,1); for(ri i=tot,p;i;--i){ p=rk[i]; if(siz[p]==1){ T1.update(1,1,n,pos[p]-len[link[p]]+1,pos[p],len[link[p]]+1); T2.update(1,1,n,pos[p]-len[p]+1,pos[p]-len[link[p]],len[p]+1); } siz[link[p]]+=siz[p],pos[link[p]]=max(pos[link[p]],pos[p]); } fill(ans+1,ans+n+1,n+1); T1.query(1,1,n,0),T2.query(1,1,n,1); for(ri i=1;i<=n;++i)cout< <<'\n'; }}sam;int main(){ scanf("%s",s+1),n=strlen(s+1); for(ri i=1;i<=n;++i)sam.expand(s[i]-'a',i); sam.solve(); return 0;}