[BZOJ 2865] 문자열 인식 접미사 자동 동기 + 선분 트 리

우선 한 번 밖 에 나타 나 지 않 은 하위 문자열 은 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<int,int> 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<int,int>::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
",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;
}