【Luogu】P 3809接尾辞並べ替え(接尾辞配列テンプレート)

タイトルリンク
今日やっと接尾辞配列テンプレートqwqを習得しました
テンプレートemmmmしかできません
まず青い本emmmmを持っています
それから青い本の221ページのコードを見てから私は理解できませんでした.
そこでrqyを出してください
　　rqy:
最初は単一の文字をソートする操作だったでしょう
c[i]は、iの値を持つ文字の数を表す
x[i]i番目の位置の優先度を示す
sa[i]は、優先度がiの文字位置を示す
最初の行は明らかに初期化され、2番目の行は明らかに統計文字の数です.
3行目にはなぜ接頭辞和が要求されるのでしょうか.
優先順位が小さいほど上位になると考えています
したがって,優先度が0のものをc[0]個,優先度が1のものをc[1]個とする.
だから、私たちはc[0]文字を「0」と仮定して、[0,c[0])区間に並んで左閉右開にしなければならない.
次に、c[1]文字を切り取って「1」と仮定し、[c[0],c[0]+c[1])区間を左閉右開に並べなければならない
そしてこのように推す
cの接頭辞とSを簡単に覚えてみましょう
そこで我々が並べ替えた区間は[0,S[0])[S[0],S[1])[S[1],S[2])になった.
ちょっと待って.
そして楽しい基数ソートができます
2つのキーワードのソート方法を考えてみましょう
つまり、私はまず第2のキーワードを並べて、それからソートアルゴリズムが安定していることを保証して、第1のキーワードを並べます.
2番目のキーワードは直接列挙することができます.第1キーワード......基数ソートはqwqを解決することができる.
次に隣接する2つの接尾辞番号が等しいかどうかを見て、等しい説明で区別できなかったら、並んで、等しくなければ退出できます.
　　

#include
#include
#include
#include
#include
#define maxn 2000100
using namespace std;
inline long long read(){
    long long num=0,f=1;
    char ch=getchar();
    while(!isdigit(ch)){
        if(ch=='-')    f=-1;
        ch=getchar();
    }
    while(isdigit(ch)){
        num=num*10+ch-'0';
        ch=getchar();
    }
    return num*f;
}

char s[maxn];
int sa[maxn];
int x[maxn];
int y[maxn];
int c[maxn];
int len;

void build(int m){
    for(int i=0;i<=m;++i)    c[i]=0;
    for(int i=1;i<=len;++i)    c[x[i]=s[i]]++;
    for(int i=1;i<=m;++i)    c[i]+=c[i-1];
    for(int i=len;i>=1;--i)    sa[c[x[i]]--]=i;
    for(int k=1;k<=len;k<<=1){
        int p=0;
        for(int i=len-k+1;i<=len;++i)    y[++p]=i;
        for(int i=1;i<=len;++i)
            if(sa[i]>k)        y[++p]=sa[i]-k;
        for(int i=0;i<=m;++i)    c[i]=0;
        for(int i=1;i<=len;++i)    c[x[y[i]]]++;
        for(int i=1;i<=m;++i)    c[i]+=c[i-1];
        for(int i=len;i>=1;--i)    sa[c[x[y[i]]]--]=y[i];
        std::swap(x,y);
        p=1;    x[sa[1]]=1;
        for(int i=2;i<=len;++i)
            x[sa[i]]=y[sa[i-1]]==y[sa[i]]&&y[sa[i-1]+k]==y[sa[i]+k]?p:++p;
        if(p>=len)    break;
        m=p;
    }
}

int main(){
    scanf("%s",s+1);
    len=strlen(s+1);
    build(200);
    for(int i=1;i<=len;++i)    printf("%d ",sa[i]);
    return 0;
}

 
転載先:https://www.cnblogs.com/cellular-automaton/p/8277739.html