水水的字符串题 ~
#include <map>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define M 500003
#define N 1000003
#define lson now<<1
#define rson now<<1|1
#define inf 1000000000
#define setIO(s) freopen(s".in","r",stdin) , freopen(s".out","w",stdout)
using namespace std;
int last,tot;
char str[N];
int rk[N],tax[N],A[N],minn[M<<2],minn2[M<<2];
struct data
{
int pre,cnt,len,id;
map<int,int>ch;
}t[N];
void Init() { last=tot=1; }
void extend(int c,int pos)
{
int np=++tot,p=last;
t[np].len=t[p].len+1,last=np;
for(;p&&!t[p].ch[c];p=t[p].pre) t[p].ch[c]=np;
if(!p) t[np].pre=1;
else
{
int q=t[p].ch[c];
if(t[q].len==t[p].len+1) t[np].pre=q;
else
{
int nq=++tot;
t[nq].len=t[p].len+1;
t[nq].id=t[q].id;
t[nq].ch=t[q].ch;
t[nq].pre=t[q].pre,t[q].pre=t[np].pre=nq;
for(;p&&t[p].ch[c]==q;p=t[p].pre) t[p].ch[c]=nq;
}
}
++t[np].cnt;
t[np].id=pos;
}
void build(int l,int r,int now)
{
minn[now]=minn2[now]=inf;
if(l==r) return;
int mid=(l+r)>>1;
if(l<=mid) build(l,mid,lson);
if(r>mid) build(mid+1,r,rson);
}
void update(int l,int r,int now,int L,int R,int v)
{
if(l>=L&&r<=R)
{
minn[now]=min(minn[now], v);
return;
}
int mid=(l+r)>>1;
if(L<=mid) update(l,mid,lson,L,R,v);
if(R>mid) update(mid+1,r,rson,L,R,v);
}
int query(int l,int r,int now,int p)
{
if(l==r) return minn[now];
int mid=(l+r)>>1,re=minn[now];
if(p<=mid) re=min(re, query(l,mid,lson,p));
else re=min(re, query(mid+1,r,rson,p));
return re;
}
void update2(int l,int r,int now,int L,int R,int v)
{
if(l>=L&&r<=R)
{
minn2[now]=min(minn2[now], v);
return;
}
int mid=(l+r)>>1;
if(L<=mid) update2(l,mid,lson,L,R,v);
if(R>mid) update2(mid+1,r,rson,L,R,v);
}
int query2(int l,int r,int now,int p)
{
if(l==r) return minn2[now];
int mid=(l+r)>>1, re=minn2[now];
if(p<=mid) re=min(re,query2(l,mid,lson,p));
else re=min(re, query2(mid+1,r,rson,p));
return re;
}
int main()
{
// setIO("input");
int n,i,j;
Init();
scanf("%s",str+1);
n=strlen(str+1);
for(i=1;i<=n;++i) extend(str[i]-'a',i);
for(i=1;i<=tot;++i) ++tax[t[i].len];
for(i=1;i<=tot;++i) tax[i]+=tax[i-1];
for(i=1;i<=tot;++i) rk[tax[t[i].len]--]=i;
build(1,n,1);
for(i=tot;i>1;--i)
{
int u=rk[i];
t[t[u].pre].cnt+=t[u].cnt;
t[t[u].pre].id=t[u].id;
if(t[u].cnt==1)
{
update(1,n,1,t[u].id-t[u].len+1,t[u].id-t[t[u].pre].len,t[u].id);
update2(1,n,1,t[u].id-t[t[u].pre].len,t[u].id,t[t[u].pre].len+1);
}
}
for(i=1;i<=n;++i) printf("%d
",min(query(1,n,1,i)-i+1, query2(1,n,1,i)));
return 0;
}