思路:
我们建立原串的后缀树,那么发现出现次数为1的子串仅能出现在叶子节点上的父亲边上.(说起来很容易)
然后发现每一个更新可以分解为两端,每一段可以相当于一条斜率恒定的线段.
因此我们将两段分开,按照截距从小到大排序,并用并查集模拟覆盖即可.
(说起来很容易)
#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
#define N 100010
struct Node{
Node*tranc[26],*pa;int len,begin,siz,deg;
Node(){}
Node(int _len,int _begin):len(_len),begin(_begin){}
}Tnull,*null=&Tnull,mem[N<<1],*P=mem,*root,*last;
Node*Newnode(int _len,int _begin){
P->len=_len,P->begin=_begin;for(int i=0;i<26;++i)P->tranc[i]=null;P->pa=null;return P++;
}
char s[N];
struct Interval{
int l,r,k;
Interval(){}
Interval(int _l,int _r,int _k):l(_l),r(_r),k(_k){}
bool operator<(const Interval&B)const{return k<B.k;}
}S[N],S2[N];
int r[N];
inline void reset(int n){
for(register int i=1;i<=n+1;++i)r[i]=i;
}
inline int find(int x){
int q=x,rq;for(;x!=r[x];x=r[x]);for(;q!=x;q=rq)rq=r[q],r[q]=x;return x;
}
int v[N],vv[N];
Node*q[N<<1];int fr,ta;
int main(){
scanf("%s",s+1);int l=strlen(s+1);
register int i,j;int y;Node*p,*np,*q,*nq;
for(last=root=Newnode(0,0),i=l;i>=1;--i){
np=Newnode(last->len+1,i);np->siz=1;
for(p=last,y=s[i]-'a';p!=null&&p->tranc[y]==null;p=p->pa)p->tranc[y]=np;
if(p==null)np->pa=root;
else{
q=p->tranc[y];
if(q->len==p->len+1)np->pa=q;
else{
nq=Newnode(p->len+1,0);nq->pa=q->pa,q->pa=np->pa=nq;
memcpy(nq->tranc,q->tranc,sizeof q->tranc);
for(;p!=null&&p->tranc[y]==q;p=p->pa)p->tranc[y]=nq;
}
}last=np;
}
for(p=mem;p<P;++p)++p->pa->deg;
for(p=mem;p<P;++p)if(p->deg==0)::q[ta++]=p;
while(fr^ta){
p=::q[fr++];
if(p->pa!=null){
p->pa->siz+=p->siz;
if(!--p->pa->deg)
::q[ta++]=p->pa;
}
}
int id=0,id2=0;
for(p=mem;p<P;++p){
if(p->siz==1){
//printf("%d %d %d\n",p->begin,p->len,p->pa->len);
S[++id]=Interval(l-(p->len-p->pa->len)+1,l,1-p->begin);
S2[++id2]=Interval(p->begin,S[id].l-1,S[id].l-p->begin+1);
}
}sort(S+1,S+id+1),sort(S2+1,S2+id2+1);
reset(l);
memset(v,0x3f,sizeof v);
for(i=1;i<=id;++i){
for(j=find(S[i].l);j<=S[i].r;j=r[j]){
if(v[j]==0x3f3f3f3f)v[j]=S[i].k;
r[j]=find(j+1);
}
}
reset(l);
memset(vv,0x3f,sizeof vv);
for(i=1;i<=id2;++i){
for(j=find(S2[i].l);j<=S2[i].r;j=r[j]){
if(vv[j]==0x3f3f3f3f)vv[j]=S2[i].k;
r[j]=find(j+1);
}
}
for(i=1;i<=l;++i)printf("%d\n",min(l,min(v[i]+i,vv[i])));
return 0;
}