108 后缀数组(SA)

视频链接：

#include 
#include 
#include 
using namespace std;

const int N = 1000010;
int n, m = 122; //把z的ASC码122，作为桶个数的初始值
char s[N];
int sa[N], c[N], x[N], y[N];
int height[N], rk[N];

void get_sa(){
    // 把后缀按第一个字母排序--sa[]
    for (int i = 1; i <= m; i++) c[i] = 0; // 清空桶
    for (int i = 1; i <= n; i++) c[x[i] = s[i]] ++;
    for (int i = 2; i <= m; i++) c[i] += c[i-1];
    for (int i = n; i; i -- ) sa[c[x[i]] --] = i;
    
    for (int k = 1; k <= n; k <<= 1) { // 循环logn轮
        // 把后缀按第二关键字排序--y[]
        int p = 0;
        for(int i = n-k+1; i <= n; i++) y[++p] = i; 
        for(int i = 1; i <= n; i++) 
            if(sa[i] > k) y[++ p] = sa[i]-k;
              // 后缀sa[i]是后缀sa[i]-k的第二关键字
              
        // 把后缀按双关键字排序--sa[]
        for(int i=1; i <= m; i++) c[i] = 0;
        for(int i=1; i <= n; i++) c[x[i]] ++;
        for(int i=2; i <= m; i++) c[i] += c[i-1];
        for(int i=n; i; i--) sa[c[x[y[i]]]--] = y[i];
             // 后缀y[i]--桶号x[]--排名c[]--生成sa[]
             
        // 把后缀按双关键字放入桶--x[]
        swap(x, y);
        x[sa[1]] = 1, p = 1;
        for (int i = 2; i <= n; i++)
            x[sa[i]]= (y[sa[i]]==y[sa[i-1]]
                    &&y[sa[i]+k]==y[sa[i-1]+k])?p:++p;
        m = p; //更新桶的个数
        if(m == n) break; //桶数等于后缀数，说明已排好
    }
}
void get_height(){
    for(int i = 1; i <= n; i++) rk[sa[i]] = i;
    for(int i=1, k=0; i <= n; i++){ //枚举后缀i
        if(rk[i] == 1) continue; //第一名height为0
        if(k) k--; //上一个后缀的height值减1
        int j = sa[rk[i]-1]; //找出后缀i的前邻后缀j
        while(i+k<=n && j+k<=n && s[i+k]==s[j+k])k++;
        height[rk[i]] = k;
        // printf("i=%d j=%d h[rk[%d]]=%d\n",i,j,i,k);
    }
}
int main(){
    scanf("%s", s+1);
    n = strlen(s+1);
    get_sa();
    get_height();
    for(int i=1; i<=n; i++) printf("%d ", sa[i]);
    puts("");
    for(int i=1; i<=n; i++) printf("%d ", height[i]);
    return 0;
}