#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#define maxn 100005
#define inf 100000000
using namespace std;
char st[maxn];
int n,tot,last,root,sum[maxn<<],tmp[maxn<<],fa[maxn<<],son[maxn<<][],dist[maxn<<],ri[maxn<<],pos[maxn<<];
struct Tsegment{
void prepare(){tot=last=root=,memset(ri,,sizeof(ri));}
int newnode(int x){
dist[++tot]=x; return tot;
}
void add(int op,int x){
int p=last,np=newnode(dist[p]+); last=np; ri[np]=; pos[np]=op;
for (;p&&!son[p][x];p=fa[p]) son[p][x]=np;
if (p==) fa[np]=root;
else{
int q=son[p][x];
if (dist[p]+==dist[q]) fa[np]=q;
else{
int nq=newnode(dist[p]+);
memcpy(son[nq],son[q],sizeof(son[q]));
fa[nq]=fa[q],fa[q]=fa[np]=nq;
for (;p&&son[p][x]==q;p=fa[p]) son[p][x]=nq;
}
}
}
}SAM;
struct Fsegment{
int l,r,lazy,val;
}tree1[maxn*];
struct date{
void build(int k,int l,int r){
tree1[k].lazy=tree1[k].val=inf; tree1[k].l=l,tree1[k].r=r;
if (l==r) return;
int mid=(l+r)/;
build(k*,l,mid),build(k*+,mid+,r);
}
void change(int k,int l,int r,int x,int y,int z){
if (x>y) return;
if (tree1[k].lazy!=inf){
if (tree1[k*].l) pushdown(k*,tree1[k].lazy);
if (tree1[k*+].l) pushdown(k*+,tree1[k].lazy);
tree1[k].lazy=inf;
}
if (l>=x&&r<=y){
pushdown(k,z);
return;
} int mid=(l+r)/;
if (x<=mid) change(k*,l,mid,x,y,z);
if (y>mid) change(k*+,mid+,r,x,y,z);
}
void pushdown(int k,int x){
tree1[k].lazy=min(tree1[k].lazy,x);
if (tree1[k].l==tree1[k].r) tree1[k].val=min(tree1[k].val,tree1[k].lazy);
}
int query(int k,int l,int r,int x){
if (tree1[k].lazy!=inf){
if (tree1[k*].l) pushdown(k*,tree1[k].lazy);
if (tree1[k*+].l) pushdown(k*+,tree1[k].lazy);
tree1[k].lazy=inf;
}
if (l==r&&r==x) return tree1[k].val;
int mid=(l+r)>>,ans=inf;
if (x<=mid) ans=min(ans,query(k*,l,mid,x));
else ans=min(ans,query(k*+,mid+,r,x));
return ans;
}
}Tree1;
struct Ksegment{
int l,r,val,lazy;
}tree[maxn*];
struct Graph{
void build(int k,int l,int r){
tree[k].l=l,tree[k].r=r,tree[k].lazy=tree[k].val=inf;
if (l==r) return; int mid=(l+r)/;
build(k*,l,mid),build(k*+,mid+,r);
}
void change(int k,int l,int r,int x,int y,int z){
if (x>y) return;
if (tree[k].lazy!=inf){
if (tree[k*].l) pushdown(k*,tree[k].lazy);
if (tree[k*+].l) pushdown(k*+,tree[k].lazy);
tree[k].lazy=inf;
}
if (l>=x&&r<=y){
pushdown(k,z);
return;
} int mid=(l+r)>>;
if (x<=mid) change(k*,l,mid,x,y,z);
if (y>mid) change(k*+,mid+,r,x,y,z);
}
void pushdown(int k,int x){
tree[k].lazy=min(tree[k].lazy,x);
if (tree[k].l==tree[k].r) tree[k].val=min(tree[k].val,tree[k].lazy);
}
int query(int k,int l,int r,int x){
if (tree[k].lazy!=inf){
if (tree[k*].l) pushdown(k*,tree[k].lazy);
if (tree[k*+].r) pushdown(k*+,tree[k].lazy);
tree[k].lazy=inf;
}
if (l==r&&r==x) return tree[k].val;
int mid=(l+r)>>,ans=inf;
if (x<=mid) ans=min(ans,query(k*,l,mid,x));
else ans=min(ans,query(k*+,mid+,r,x));
return ans;
}
}Tree;
int main(){
scanf("%s",st+),n=strlen(st+);
SAM.prepare();
for (int i=;i<=n;i++) SAM.add(i,st[i]-'a');
memset(sum,,sizeof(sum));
for (int i=;i<=tot;i++) sum[dist[i]]++;
for (int i=;i<=tot;i++) sum[i]+=sum[i-];
for (int i=;i<=tot;i++) tmp[sum[dist[i]]--]=i;
for (int i=tot,x;i>=;i--){
x=tmp[i];
if (fa[x]) ri[fa[x]]+=ri[x];
}
ri[root]=;
Tree1.build(,,n);
Tree.build(,,n);
for (int i=;i<=tot;i++){
if (ri[i]!=) continue;
int x=pos[i],y=dist[i],z=dist[fa[i]]+;
Tree1.change(,,n,x-y+,x-z+,x); //第一棵线段树按位置,记得减
Tree.change(,,n,x-z+,x,z); //第二棵线段树按长度
}
for (int i=;i<=n;i++){
printf("%d\n",min(Tree1.query(,,n,i)-i+,Tree.query(,,n,i)));
}
return ;
}
题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1396
题目大意：
做法；看到题目中所说的T在S中只出现过一次，就很容易想到用后缀自动机嘛，显然就是right值为一的状态，而且right值为一的状态只能是每次add时第一个新建的点，这很显然嘛，这就很方便记录了。然后再用线段树维护一下最小值，稍微想一下就行，当时我竟然是很快就想到了，不过我inf开小了，狂WA不止。
后缀自动机+线段树。