bzoj千题计划319:bzoj2865: 字符串识别(后缀自动机 + 线段树)

时间:2021-08-21 08:42:37

https://www.lydsy.com/JudgeOnline/problem.php?id=2865

同上一篇博客

就是卡卡空间,数组改成map

#include<map>
#include<cstdio>
#include<cstring>
#include<algorithm> #define N 500001 using namespace std; char s[N]; map<int,int>ch[N<<];
int tot=; int fa[N<<],len[N<<];
int siz[N<<];
int last=,p,q,np,nq; int leaf[N]; int v[N],sa[N<<]; struct Segment
{
int mx[N<<];
int tag[N<<]; void down(int k)
{
mx[k<<]=min(mx[k<<],tag[k]);
mx[k<<|]=min(mx[k<<|],tag[k]);
tag[k<<]=min(tag[k<<],tag[k]);
tag[k<<|]=min(tag[k<<|],tag[k]);
tag[k]=2e9;
} void build(int k,int l,int r)
{
mx[k]=tag[k]=2e9;
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 opl,int opr,int w)
{
if(l>=opl && r<=opr)
{
mx[k]=min(mx[k],w);
tag[k]=min(tag[k],w);
return;
}
int mid=l+r>>;
if(tag[k]!=2e9) down(k);
if(opl<=mid) change(k<<,l,mid,opl,opr,w);
if(opr>mid) change(k<<|,mid+,r,opl,opr,w);
mx[k]=min(mx[k<<],mx[k<<|]);
} int query(int k,int l,int r,int x)
{
if(l==r) return mx[k];
int mid=l+r>>;
if(tag[k]!=2e9) down(k);
if(x<=mid) return query(k<<,l,mid,x);
return query(k<<|,mid+,r,x);
}
}; Segment tr1,tr2; void extend(int c)
{
len[np=++tot]=len[last]+;
siz[tot]=;
for(p=last;p && ch[p].find(c)==ch[p].end();p=fa[p]) ch[p][c]=np;
if(!p) fa[np]=;
else
{
q=ch[p][c];
if(len[q]==len[p]+) fa[np]=q;
else
{
nq=++tot;
fa[nq]=fa[q];
ch[nq]=ch[q];
fa[q]=fa[np]=nq;
len[nq]=len[p]+;
for(;ch[p][c]==q;p=fa[p]) ch[p][c]=nq;
}
}
last=np;
} int main()
{
scanf("%s",s+);
int n=strlen(s+);
for(int i=;i<=n;++i)
{
leaf[i]=tot+;
extend(s[i]-'a');
}
for(int i=;i<=tot;++i) v[len[i]]++;
for(int i=;i<=n;++i) v[i]+=v[i-];
for(int i=;i<=tot;++i) sa[v[len[i]]--]=i;
int x;
for(int i=tot;i;--i)
{
x=sa[i];
siz[fa[x]]+=siz[x];
}
tr1.build(,,n);
tr2.build(,,n);
int l,r,end;
for(int x=;x<=tot;++x)
if(siz[x]==)
{
l=len[fa[x]];
r=len[x];
end=len[x];
tr1.change(,,n,end-l,end,l+);
tr2.change(,,n,end-r+,end-l,end+);
}
int a,b;
for(int i=;i<=n;++i)
{
a=tr1.query(,,n,i);
b=tr2.query(,,n,i)-i;
printf("%d\n",min(a,b));
}
return ;
}