设母串为$S$

在SAM里，一个节点$s$代表的字符串仅出现一次$\rightarrow\ s$到终点只有一条路$\rightarrow$没有节点$x$使得$fa_x=s$

定义$max_s$表示从起点走到$s$的最长路，我们可以找到一个仅出现一次的长度为$max_s$的$S$的前缀

而是它的后缀且出现多次的最大长度是$max_{fa_s}$，设$r=max_s,l=r-max_{fa_s}$

因为要覆盖$[l,r]$，所以对于$i\in[1,l)$，贡献答案为$r-i+1$，对于$i\in[l,r]$，贡献答案为$r-l+1$

用两棵区间取max的线段树，对于含$i$的在最后统计答案时减去$i$即可

#include
     
      #include
      
       struct sam{	int ch[26],fa,v;}t[200010];int las=1,M=1;void extend(int c){	int p=las,np=++M,q,nq;	t[np].v=t[p].v+1;	while(p&&t[p].ch[c]==0){		t[p].ch[c]=np;		p=t[p].fa;	}	if(p==0)		t[np].fa=1;	else{		q=t[p].ch[c];		if(t[q].v==t[p].v+1)			t[np].fa=q;		else{			nq=++M;			t[nq]=t[q];			t[nq].v=t[p].v+1;			t[np].fa=t[q].fa=nq;			while(p&&t[p].ch[c]==q){				t[p].ch[c]=nq;				p=t[p].fa;			}		}	}	las=np;}char s[100010];bool mul[200010];int n;#define inf 2147483647int min(int a,int b){return a
       
        >1;		if(L<=mid)modify(L,R,v,l,mid,x<<1);		if(mid
        
         <<1|1);	}	int query(int p,int l,int r,int x){		if(l==r)return mn[x];		pushdown(x);		int mid=(l+r)>>1;		if(p<=mid)			return query(p,l,mid,x<<1);		else			return query(p,mid+1,r,x<<1|1);	}}a,b;int main(){	int i,l,r;	gets(s+1);	n=strlen(s+1);	a.pre();	b.pre();	for(i=1;i<=n;i++)extend(s[i]-'a');	for(i=2;i<=M;i++)mul[t[i].fa]=1;	for(i=2;i<=M;i++){		if(mul[i]==0){			r=t[i].v;			l=r-t[t[i].fa].v;			if(l>1)a.modify(1,l-1,r+1,1,n,1);			b.modify(l,r,r-l+1,1,n,1);		}	}	for(i=1;i<=n;i++)printf("%d\n",min(a.query(i,1,n,1)-i,b.query(i,1,n,1)));	}