拼命给自己拉低AC率（

SAM 一发入魂

很明显 我们要查的就是 叶子结点

叶子结点 的 len 和 其父亲的 len 会影响一段区间

大概长这个样子 前面一段倾斜的 就是 len 在不断增长 后面的要取min所以就是平直的[你可能需要意会一下]

因为一个点的len是一段连续的区间 你从这个图里就可以看的比较清楚了qwq

然后我们 就重锤李超树 咳咳咳才不要李超树呢 我们发现 所有的斜线都是斜率为-1 那么我们对于斜线维护 ai+i 最后-i 就变成了直线

现在就是两种直线 我们分别用两棵线段树维护就好了

（注意：SAM中叶子节点一定是 “关键节点”[前缀节点] 而“关键节点”不一定全部都是叶子结点）

附代码。

#include
    
     #include
     
      #include
      
       #include
       
        #define inf 20021225#define ll long long#define mxn 100010#define ls(x) x<<1#define rs(x) x<<1|1using namespace std;int ans[mxn];struct segtree{	int mn[mxn*4],tag[mxn*4];	void pushdown(int x)	{		if(tag[x]
        
         >1;		build(ls(x),l,mid);build(rs(x),mid+1,r);	}	void modify(int x,int l,int r,int LL,int RR,int val)	{		if(RR
         
          =LL&&r<=RR) { mn[x] = min(mn[x],val); tag[x] = min(tag[x],val); return; } int mid=l+r>>1; pushdown(x); if(LL<=mid) modify(ls(x),l,mid,LL,RR,val); if(RR>mid) modify(rs(x),mid+1,r,LL,RR,val); pushup(x); } void query(int x,int l,int r) { if(l==r){ans[l]=mn[x];return;} int mid = l+r>>1; pushdown(x); query(ls(x),l,mid); query(rs(x),mid+1,r); }}t1,t2;struct node{int fa,len,ch[26];}t[mxn*4];int poi,rt,lt; char ch[mxn];int pos[mxn],n;void init(){ rt=lt=++poi; t1.build(1,1,n); t2.build(1,1,n);}int id(char c){return c-'a';}bool vis[mxn*4];void insert(int c,int id){ int p=lt,np=lt=++poi; t[np].len=t[p].len+1; pos[id]=np; for(;p&&!t[p].ch[c];p=t[p].fa) t[p].ch[c]=np; if(!p){t[np].fa=rt;return;} int q=t[p].ch[c]; if(t[q].len==t[p].len+1){t[np].fa=q; vis[q] =1;return;} int nq=++poi; t[nq].len=t[p].len+1; memcpy(t[nq].ch,t[q].ch,sizeof(t[q].ch)); t[nq].fa=t[q].fa; t[q].fa=t[np].fa=nq; vis[nq] = 1; for(;p&&t[p].ch[c]==q;p=t[p].fa) t[p].ch[c]=nq;}int f[mxn];void calc(){ for(int i=1;i<=n;i++) { int x=pos[i],f=t[x].fa; if(vis[x]) continue; int l2=t[x].len,l1=t[f].len+1; t1.modify(1,1,n,i-l1+1,i,l1); t2.modify(1,1,n,i-l2+1,i-l1,i+1); } t1.query(1,1,n); memcpy(f,ans,sizeof(f)); //for(int i=1;i<=n;i++) printf("%d ",ans[i]); t2.query(1,1,n); for(int i=1;i<=n;i++) ans[i]-=i,f[i]=min(f[i],ans[i]); for(int i=1;i<=n;i++) printf("%d\n",f[i]);}int main(){ scanf("%s",ch+1); n=strlen(ch+1); init(); for(int i=1;i<=n;i++) insert(id(ch[i]),i); calc(); return 0;}