Description
在这个问题中，给定一个字符串S，与一个整数K，定义S的子串T=S(i, j)是关于第K位的识别子串，满足以下两个条件：
1、i≤K≤j。
2、子串T只在S中出现过一次。
例如，S="banana"，K=5，则关于第K位的识别子串有"nana"，"anan"，"anana"，"nan"，"banan"和"banana"。
现在，给定S，求对于S的每一位，最短的识别子串长度是多少。
建SAM，|Right|=1的可以作为识别子串哦
|Right(s)|=1 出现位置就是Max(s)
考虑它可以作为哪些位置的识别子串
令r=Max(s),l=Max(s)-Max(fa)
[1,l-1]可以，贡献为r-i+1
[l,r]可以，贡献为r-l+1
用两颗线段树就行了
PS：卡空间好有意思啊
PS：给其他人考一道试机题竟然花我三个小时呜呜呜
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
#define lc x<<1
#define rc x<<1|1
#define mid ((l+r)>>1)
#define lson lc,l,mid
#define rson rc,mid+1,r
const int N=1e6+,M=5e5+,INF=1e9;
typedef long long ll;
int n;
char s[M];
struct SegmentTree{
struct node{
int mn;
node():mn(INF){}
}t[M<<];
inline void paint(int x,int v){
t[x].mn=min(t[x].mn,v);
}
inline void pushDown(int x){
if(t[x].mn!=INF){
paint(lc,t[x].mn);
paint(rc,t[x].mn);
t[x].mn=INF;
}
}
void segCov(int x,int l,int r,int ql,int qr,int v){
if(ql>qr) return;
if(ql<=l&&r<=qr) paint(x,v);
else{
pushDown(x);
if(ql<=mid) segCov(lson,ql,qr,v);
if(mid<qr) segCov(rson,ql,qr,v);
}
}
int segMin(int x,int l,int r,int p){
if(l==r) return t[x].mn;
else{
pushDown(x);
if(p<=mid) return segMin(lson,p);
else return segMin(rson,p);
}
}
}A,B;
struct node{
int ch[],par,val;
}t[N];
int sz=,root=,last=;
void extend(int c){
int p=last,np=++sz;
t[np].val=t[p].val+;
for(;p&&!t[p].ch[c];p=t[p].par) t[p].ch[c]=np;
if(!p) t[np].par=root;
else{
int q=t[p].ch[c];
if(t[q].val==t[p].val+) t[np].par=q;
else{
int nq=++sz;
t[nq]=t[q];t[nq].val=t[p].val+;
t[q].par=t[np].par=nq;
for(;p&&t[p].ch[c]==q;p=t[p].par) t[p].ch[c]=nq;
}
}
last=np;
}
int ri[N];
void solve(){
for(int i=;i<=sz;i++) ri[i]=;
for(int i=;i<=sz;i++) ri[t[i].par]=;
for(int i=;i<=sz;i++) if(ri[i]==){//printf("right %d %d %d\n",i,t[i].val,t[i].par);
int l=t[i].val-t[t[i].par].val,r=t[i].val;//printf("lr %d %d\n",l,r);
A.segCov(,,n,,l-,r+);
B.segCov(,,n,l,r,r-l+);//if(r==2) printf("bbbb %d\n",B.segMin(1,1,n,2));
}
for(int i=;i<=n;i++) printf("%d\n",min(A.segMin(,,n,i)-i,B.segMin(,,n,i)));
}
int main(){
freopen("in","r",stdin);
scanf("%s",s+);
n=strlen(s+);
for(int i=;i<=n;i++) extend(s[i]-'a');
solve();
}