BZOJ1396:识别子串 后缀自动机+并查集(&&BZOJ2865)

思路:

我们建立原串的后缀树,那么发现出现次数为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;
}