后缀自动机|[BZOJ2865]字符串识别后缀自动机+线段树

2021-11-10

【后缀自动机|[BZOJ2865]字符串识别后缀自动机+线段树】首先只出现过一次的子串，就是SAM上那些 |Right|=1 的点。
对于这些点考虑它们的最小拓展长度为 Mini=Maxfai+1 ，又因为 |Right|=1 ，所以这个点在字符串上的位置就是 Maxi 。
所以对于 [Maxi?Mini+1,Maxi] 的位置 x 有一个长度为 Mini 的可以作为答案，对于 [1,Mini] 的位置 x 有一个长度为 Maxi?x+1 的可以作为答案。
线段树区间最小值即可。
代码：

#include #include #include #include using namespace std; const int maxn=1000010; int n; char s[maxn]; struct tree { int l,r,mid,fm,fd; tree *ls,*rs; tree(){ls=rs=NULL; } void build(int lx,int rx) { l=lx; r=rx; mid=(l+r)>>1; fm=fd=0x3f3f3f3f; if(l==r) return ; (ls=new tree)->build(l,mid); (rs=new tree)->build(mid+1,r); } void mdf(int lx,int rx,int cm,int cd) { if(lx>rx) return; if(l==lx&&r==rx) {fm=min(fm,cm),fd=min(fd,cd); return; } if(rx<=mid) ls->mdf(lx,rx,cm,cd); else if(lx>mid) rs->mdf(lx,rx,cm,cd); else ls->mdf(lx,mid,cm,cd),rs->mdf(mid+1,rx,cm,cd); } int qry(int pl) { int re=min(fm,fd-pl+1); if(l==r) return re; if(pl<=mid) return min(re,ls->qry(pl)); else return min(re,rs->qry(pl)); } }*xtr; struct sam { map a[maxn]; int cnt,last,fa[maxn],ri[maxn],mx[maxn],mi[maxn],buc[maxn],ord[maxn]; sam(){cnt=last=1; } void extend(int c) { int p=last,np=last=++cnt; mx[np]=mx[p]+1; ri[np]=1; for(; p&&!a[p][c]; p=fa[p]) a[p][c]=np; if(!p) {fa[np]=1; return; } int q=a[p][c]; if(mx[q]==mx[p]+1) {fa[np]=q; return; } int nq=++cnt; mx[nq]=mx[p]+1; for(map::iterator it=a[q].begin(); it!=a[q].end(); it++) a[nq][it->first]=a[q][it->first]; fa[nq]=fa[q]; fa[q]=fa[np]=nq; for(; p&&a[p][c]==q; p=fa[p]) a[p][c]=nq; } void pre() { for(int i=1; i<=cnt; i++) buc[mx[i]]++; for(int i=1; i<=cnt; i++) buc[i]+=buc[i-1]; for(int i=1; i<=cnt; i++) ord[buc[mx[i]]--]=i; for(int i=cnt; i; i--) ri[fa[ord[i]]]+=ri[ord[i]],mi[ord[i]]=mx[fa[ord[i]]]+1; } void solve() { (xtr=new tree)->build(1,n); for(int i=2; i<=cnt; i++) if(ri[i]==1) xtr->mdf(mx[i]-mi[i]+1,mx[i],mi[i],0x3f3f3f3f),xtr->mdf(1,mx[i]-mi[i],0x3f3f3f3f,mx[i]); for(int i=1; i<=n; i++) printf("%d\n",xtr->qry(i)); } }Tsam; int main() { scanf("%s",s+1); n=strlen(s+1); for(int i=1; i<=n; i++) Tsam.extend(s[i]-'a'); Tsam.pre(); Tsam.solve(); return 0; }

推荐阅读

上一篇：ジ﹋★☆『|Java 公约数

下一篇：【国家集训队2012】【BZOJ2738】矩阵乘法