zcmimi's blog
查看原题

点击跳转

看到环就想到把原串变成两倍,而这对被延长了的原串中的子串在sa中的排名没有影响

比如baba变成babadfasdfa,这并不会影响到baba的排名

那么直接求出sa后输出即可

#include<bits/stdc++.h>
const int N=200011;
char s[N];
int n,m,sa[N],rnk[N],tax[N],tp[N];
void qsort(){
    for(int i=0;i<=m;++i)tax[i]=0;
    for(int i=1;i<=n;++i)++tax[rnk[i]];
    for(int i=1;i<=m;++i)tax[i]+=tax[i-1];
    for(int i=n;i;--i)sa[tax[rnk[tp[i]]]--]=tp[i];
}
void suffix(){
    m=300;
    for(int i=1;i<=n;++i)sa[i]=0,rnk[i]=s[i],tp[i]=i;
    qsort();
    for(int w=1,p=0;p<n;m=p,w<<=1){
        p=0;
        for(int i=1;i<=w;++i)tp[++p]=n-w+i;
        for(int i=1;i<=n;++i)
            if(sa[i]>w)tp[++p]=sa[i]-w;
        qsort();
        std::swap(tp,rnk);
        rnk[sa[1]]=p=1;
        for(int i=2;i<=n;++i)
            rnk[sa[i]]=p+=tp[sa[i]]^tp[sa[i-1]]||tp[sa[i]+w]^tp[sa[i-1]+w];
    }
}
int main(){
    scanf("%s",s+1),n=strlen(s+1);
    for(int i=1;i<=n;++i)s[i+n]=s[i];
    n<<=1;
    suffix();
    for(int i=1;i<=n;++i)if(sa[i]<=(n>>1))
        putchar(s[sa[i]+(n>>1)-1]);
}
LG 4051 [JSOI2007]字符加密
comment评论
Search
search