题目描述：
算法标签：后缀自动机
思路：
一个串在后缀自动机中sz为1，即可对答案做出贡献，我们考虑可以造成哪几种贡献：
minnlen=d[fa[x]]+1,maxnlen=d[x].
1.对于区间[endpos-maxnlen,endpos-minnlen]，贡献是endpos+1-i.
2.对于区间[endpos-minnlen,endpos],贡献是minnlen.
用两棵线段树统计答案即可。
以下代码：
#include<bits/stdc++.h> #define il inline using namespace std; const int N=2e5+5; char s[N];int n,cnt=1,cur=1,last,ch[N][26],d[N],fa[N],mn[N<<1],a[N],c[N],sz[N],r[N],b[N<<1],end[N]; il void build(int c,int id){ last=cur;cur=++cnt;d[cur]=id; int p=last;end[cur]=id; for(;p&&!ch[p][c];p=fa[p])ch[p][c]=cur; if(!p)fa[cur]=1; else{ int q=ch[p][c]; if(d[q]==d[p]+1)fa[cur]=q; else{ int nt=++cnt;d[nt]=d[p]+1; memcpy(ch[nt],ch[q],sizeof(ch[q])); fa[nt]=fa[q];fa[q]=fa[cur]=nt; for(;ch[p][c]==q;p=fa[p])ch[p][c]=nt; } } sz[cur]=1; } il void init(int x,int l,int r){ mn[x]=N;b[x]=N;if(l==r)return;int mid=(l+r)>>1; init(x<<1,l,mid);init(x<<1|1,mid+1,r); } il void C(int x,int l,int r,int ql,int qr,int v){ if(ql<=l&&r<=qr){mn[x]=min(mn[x],v);return;} int mid=(l+r)>>1; if(ql<=mid)C(x<<1,l,mid,ql,qr,v); if(mid<qr)C(x<<1|1,mid+1,r,ql,qr,v); } il void C2(int x,int l,int r,int ql,int qr,int v){ if(ql<=l&&r<=qr){b[x]=min(b[x],v);return;} int mid=(l+r)>>1; if(ql<=mid)C2(x<<1,l,mid,ql,qr,v); if(mid<qr)C2(x<<1|1,mid+1,r,ql,qr,v); } il int q1(int x,int l,int r,int pos){ if(l==r)return mn[x];int mid=(l+r)>>1; if(pos<=mid)return min(q1(x<<1,l,mid,pos),mn[x]); else return min(q1(x<<1|1,mid+1,r,pos),mn[x]); } il int q2(int x,int l,int r,int pos){ if(l==r)return b[x];int mid=(l+r)>>1; if(pos<=mid)return min(q2(x<<1,l,mid,pos),b[x]); else return min(q2(x<<1|1,mid+1,r,pos),b[x]); } int main() { scanf(" %s",s+1);n=strlen(s+1); for(int i=1;i<=n;i++)build(s[i]-'a',i); for(int i=1;i<=cnt;i++)c[d[i]]++; for(int i=1;i<=n;i++)c[i]+=c[i-1]; for(int i=cnt;i;i--)a[c[d[i]]--]=i;init(1,1,n); for(int i=cnt;i;i--){ sz[fa[a[i]]]+=sz[a[i]];end[fa[a[i]]]=end[a[i]]; if(sz[a[i]]==1){ int mnl=d[fa[a[i]]]+1,mnr=d[a[i]]; C(1,1,n,end[a[i]]-mnr+1,end[a[i]]-mnl+1,end[a[i]]+1); C2(1,1,n,end[a[i]]-mnl+1,end[a[i]],mnl); } } for(int i=1;i<=n;i++){ int res=q1(1,1,n,i)-i; printf("%d ",min(res,q2(1,1,n,i))); } return 0; }