题目
Description
Input
一行,一个由小写字母组成的字符串S,长度不超过10^5
Output
L行,每行一个整数,第i行的数据表示关于S的第i个元素的最短识别子串有多长.
Sample Input
agoodcookcooksgoodfood
Sample Output
1
2
3
3
2
2
3
3
2
2
3
3
2
1
2
3
3
2
1
2
3
4
题解
有个挺显然的结论：
$SAM$中如果一个状态$i$的$right$集合为$1$，那么这个子串在原串中的位置为$len_i$
所以对于一个$right$集合为$1$的状态$i$，最长长度为$max_i(len_i)$，最短长度为$min_i$，分两种情况讨论：
- 对于$[1,max_i-min_i)$中某个位置$j$，最短的子串是$max_i-j+1$
- 对于$[max_i-min_i,max_i]$中某个位置$j$，最短子串是$max_i-min_i+1$
这样可以维护两棵线段树，单点查询即可
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# include<algorithm>
# define tl (k<<1)
# define tr (k<<1|1)
# define mid (l+r>>1)
using namespace std;
const int MAX=2e5+5;
struct Segment_Tree{
struct p{
int x,tag;
p() {x=tag=1e9;}
}s[MAX<<1];
void down(int k)
{
if(s[k].tag!=1e9)
{
int F=s[k].tag;
s[tl].tag=min(s[tl].tag,F),s[tr].tag=min(s[tr].tag,F),s[tl].x=min(s[tl].x,F),s[tr].x=min(s[tr].x,F);
}
}
void change(int l,int r,int k,int L,int R,int dis)
{
if(l>R||L>r) return;
s[k].x=min(s[k].x,dis);
if(l>=L&&r<=R) return void(s[k].tag=min(s[k].tag,dis));
down(k),change(l,mid,tl,L,R,dis),change(mid+1,r,tr,L,R,dis);
}
int ask(int l,int r,int k,int x)
{
if(l==r) return s[k].x;
down(k);
if(x<=mid) return ask(l,mid,tl,x);
return ask(mid+1,r,tr,x);
}
}Tree,_Tree;
int n;
char a[MAX];
struct SAM{
int l,r,L;
int len[MAX],fa[MAX],siz[MAX],tax[MAX],id[MAX];
int son[MAX][26];
SAM() {l=r=1;}
void ins(int x)
{
int tt=r;
len[r=++l]=++L,siz[r]=1;
for(;tt&&!son[tt][x];tt=fa[tt])
son[tt][x]=r;
if(!tt) return void(fa[r]=1);
int qwq=son[tt][x];
if(len[qwq]==len[tt]+1) return void(fa[r]=son[tt][x]);
len[++l]=len[tt]+1;
for(int i=0;i<26;++i)
son[l][i]=son[qwq][i];
fa[l]=fa[qwq],fa[qwq]=fa[r]=l;
for(int i=tt;son[i][x]==qwq;i=fa[i])
son[i][x]=l;
}
void Solve()
{
for(int i=1;i<=l;++i)
++tax[len[i]];
for(int i=1;i<=n;++i)
tax[i]+=tax[i-1];
for(int i=l;i>=1;--i)
id[tax[len[i]]--]=i;
for(int i=l;i>=1;--i)
siz[fa[id[i]]]+=siz[id[i]];
for(int i=2,L,R;i<=l;++i)
if(siz[i]==1) L=len[i]-len[fa[i]],R=len[i],Tree.change(1,n,1,1,L-1,R),_Tree.change(1,n,1,L,R,R-L+1);
for(int i=1;i<=n;++i)
printf("%d\n",min(Tree.ask(1,n,1,i)-i+1,_Tree.ask(1,n,1,i)));
}
}SAM;
int main()
{
scanf("%s",a),n=strlen(a);
for(int i=0;i<n;++i)
SAM.ins(a[i]-'a');
return SAM.Solve(),0;
}
