P3809 后缀排序(倍增法后缀数组)

• 问题
• 分析
• 代码

• P3809 后缀排序 - https://www.luogu.com.cn/problem/P3809

• 基数排序
• 第2关键字排序后，再对第1关键字分桶
• 然后再按第2关键字的（逆）序遍历，即可将第1关键字的同一桶内元素排序

// 排名(rank)：有并列的序号, 例如：0、0、1、2、2，……
// 排序：无并列的序号，例如：0、1、2、3、4、5、…… 
#include
using namespace std;
const int MXN = 1e6+10;
char s[MXN];    // 字符串
int n;          // 字符串长度
int fir[MXN];   // 第1关键字排名, 下标 -> 排名；fir[i]：下标为i的后缀的排名为fir[i]
int sec[MXN];   // 第2关键字排序, 序号 -> 下标；sec[i]：序号为i的后缀的下标为sec[i]
int c[MXN];     // 对第1关键字的排名计数
int sa[MXN];    // 是当前第1和第2关键字的总排序，也是下一次的第1关键字序
void calc_sa(){
    int *x = fir, *y = sec, m = 256;
    // for(int i = 0; i < n; ++i) x[i] = s[i] ; // x: 第1关键字排名
    for(int i = 0; i < m; ++i) c[i] = 0;
    for(int i = 0; i < n; ++i) ++c[x[i] = s[i]]; // 第1关键字计数
    for(int i = 1; i < m; ++i) c[i] += c[i-1];
    for(int i = n-1; i >= 0; --i) sa[--c[x[i]]] = i; // 下标从0开始
    for(int p, k = 1; k <= n; k <<= 1){
        
        p = 0; // 第2关键字的序号
        for(int i = n-k; i < n; ++i) y[p++] = i; // 无第2关键字，序最小
        // 按序i遍历, sa[i]（位置）在[0, k-1]内的不能成为第2关键字;否则是位置sa[i]-k的第2关键字序
        for(int i = 0; i < n; ++i) if(sa[i] >= k) y[p++] = sa[i] - k; // 序号转换：i -> p
        
        
        for(int i = 0; i < m; ++i) c[i] = 0;
        for(int i = 0; i < n; ++i) ++c[x[i]];        // 对第1关键字排名计数
        // for(int i = 0; i < n; ++i) ++c[x[sa[i]]]; // 对第1关键字排名计数
        // for(int i = 0; i < n; ++i) ++c[x[y[i]]];  // 对第1关键字排名计数（参考资料基本此法）
        for(int i = 0; i < m; ++i) c[i] += c[i-1];
        for(int i = n-1; i >= 0; --i) sa[--c[x[y[i]]]] = y[i];// 按第2关键字的序遍历，得到第1、2关键字的序

        // 获取本次排序结果的排名，它是下一次的第1关键字排名，为下一轮排序做准备
        swap(x, y); // 交换：第1关键字的排名 和 第2关键字的排序；
        p = 1, x[sa[0]] = 0;
        for(int i = 1; i < n; ++i)  // 第1、2关键字排名相同，则排名并列
            x[sa[i]] = (y[sa[i-1]] == y[sa[i]] && y[sa[i-1]+k] == y[sa[i]+k])?p-1:p++;
       
        if(p >= n) break; // 所有后缀长度不一，排名必然不一，即p必可以到n
        m = p;
    }
}
int main(){
    scanf("%s", s);
    n = strlen(s), calc_sa();
    for(int i = 0; i < n-1; ++i) printf("%d ", sa[i]+1);
    printf("%dn", sa[n-1]+1);
    return 0;
}