在这个问题中，给定一个字符串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：卡空间好有意思啊
#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+5,M=5e5+5,INF=1e9; typedef long long ll; int n; char s[M]; struct SegmentTree{ struct node{ int mn; node():mn(INF){} }t[M<<2]; 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[26],par,val; }t[N]; int sz=1,root=1,last=1; void extend(int c){ int p=last,np=++sz; t[np].val=t[p].val+1; 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+1) t[np].par=q; else{ int nq=++sz; t[nq]=t[q];t[nq].val=t[p].val+1; 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=1;i<=sz;i++) ri[i]=1; for(int i=1;i<=sz;i++) ri[t[i].par]=0; for(int i=1;i<=sz;i++) if(ri[i]==1){//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(1,1,n,1,l-1,r+1); B.segCov(1,1,n,l,r,r-l+1);//if(r==2) printf("bbbb %d\n",B.segMin(1,1,n,2)); } for(int i=1;i<=n;i++) printf("%d\n",min(A.segMin(1,1,n,i)-i,B.segMin(1,1,n,i))); } int main(){ freopen("in","r",stdin); scanf("%s",s+1); n=strlen(s+1); for(int i=1;i<=n;i++) extend(s[i]-‘a‘); solve(); }