改良板子

namespace SA{
    #define _rep(i, x, y) for(int i = (int)x; i < (int)y; ++ i)
    #define _dep(i, x, y) for(int i = (int)x; i > (int)y; -- i)
    const int N = 3e5 + 10;
    // sa[i] 为排名为i的后缀编号, rk[i]为后缀编号为i的后缀的排名, height[i]为排名i + 1与 i的最长公共前缀
    int sa[N], rk[N], id[N], px[N], cnt[N], oldrk[N], height[N];
    bool cmp(int x, int y, int w){
        return oldrk[x] == oldrk[y] && oldrk[x + w] == oldrk[y + w];
    }
    void get_sa(string s){
        int n = s.size();
        s = "$" + s;
        //'$'的字典序比'a'~'z'的字典序都小,用来做哨兵
        int m = 300, p, i;// 值域 
        _rep(i, 1, n + 1) ++ cnt[rk[i] = s[i]];
        _rep(i, 1, m + 1) cnt[i] += cnt[i - 1];
        _dep(i, n, 0) sa[cnt[rk[i]] --] = i;
        for(int w = 1; w < n; w <<= 1, m = p){
            for(p = 0, i = n; i > n - w; i --) id[++ p] = i;
            _rep(i, 1, n + 1) if(sa[i] > w) id[++ p] = sa[i] - w;
            memset(cnt, 0, sizeof cnt);
            _rep(i, 1, n + 1) ++ cnt[px[i] = rk[id[i]]];
            _rep(i, 1, m + 1) cnt[i] += cnt[i - 1];
            _dep(i, n, 0) sa[cnt[px[i]] --] = id[i];
            memcpy(oldrk, rk, sizeof rk);
            p = 0;
            _rep(i, 1, n + 1) rk[sa[i]] = cmp(sa[i], sa[i - 1], w) ? p : ++ p;
        }
    }
    void get_height(string s){ // 先求出SA在求height
        int n = s.size();
        s = "$" + s;
        int k = 0;
        _rep(i, 1, n + 1){
            int idx = rk[i];
            if(idx == 1) continue;
            int j = sa[idx - 1];
            while(s[i + k] == s[j + k]) k ++;
            height[idx] = k;
            k = max(k - 1, 0);
        }
    }
}

非哈希解法 O(2nlogn) + O(n)

#include<bits/stdc++.h>
using namespace std;
const int N = 3000010;
int sa[N], height[N], rk[N << 1], oldrk[N << 1];
//sa[i]记录所有后缀排序后第i小的后缀的编号,rk[i]表示后缀i的排名
char s[N];
int main(){
    scanf("%s", s);
    int n = strlen(s);
    s[n++] = '$';//'$'的字典序比'a'~'z'的字典序都小,用来做哨兵
    for(int i = 0; i < n; i ++) sa[i] = i, rk[i] = s[i];
    int k = 0;
    while((1 << k) < n){//倍增
        sort(sa, sa + n, [&](const int& x, const int& y){
            return rk[x] == rk[y] ? rk[x + (1 << k)] < rk[y + (1 << k)] : rk[x] < rk[y];
        });
        memcpy(oldrk,rk,sizeof(rk));
        //更新rk数组
        oldrk[sa[0]] = rk[sa[0]] = 0;
        for(int i = 1, rank = 0; i < n; i++){
           if(oldrk[sa[i]] == oldrk[sa[i - 1]] and oldrk[sa[i] + (1 << k)] == oldrk[sa[i - 1] + (1 << k)])
               rk[sa[i]] = rank;
           else rk[sa[i]] = ++rank;
        }
        k++;
    }
    k = 0;
    for(int i = 0; i < n - 1; i ++){
        int idx = rk[i];
        int j = sa[idx - 1];
        while(s[i + k] == s[j + k]) k++;
        height[idx] = k;
        k = max(k - 1, 0);
    }
    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;
}

基数排序做法

#include<bits/stdc++.h>
using namespace std;
#define _rep(i, x, y) for(int i = (int)x; i < (int)y; ++i)
#define _dep(i,x,y) for(int i = (int)x; i > (int)y; i--)
#define all(x) (x).begin(), (x).end()
#define cmp(x, y, l) (oldrk[x] == oldrk[y] && oldrk[x + l] == oldrk[y + l])
typedef long long ll;
typedef vector<int> VI;
int main(){
    ios::sync_with_stdio(false); cin.tie(0);
    string s;
    cin >> s;
    int n = s.size();
    int m = 257;//初始值域
    VI rk(n), oldrk(n << 1, -1), cnt(max(m, n + 1)), sa(n); // oldrk记得初始为-1表示无穷小，否则会与原rk的0值冲突
    _rep(i, 0, n) ++ cnt[rk[i] = s[i]];
    _rep(i, 1, m) cnt[i] += cnt[i - 1];
    _dep(i, n - 1, -1) sa[-- cnt[rk[i]]] = i;
    VI id(n);
    int p = 0;
    VI px(n);
    int len;
    for(len = 1; len < n; len <<= 1,m = p + 1){//更新值域
        p = 0;
        _dep(i, n - 1, n - len - 1) id[p ++] = i;//把第二关键字为空的串放前面
        _rep(i, 0, n) if(sa[i] >= len) id[p ++] = sa[i] - len;// 按第二关键字排序
        fill(all(cnt), 0);
        _rep(i, 0, n) ++ cnt[px[i] = rk[id[i]]];    
        _rep(i, 1, m) cnt[i] += cnt[i - 1];
        _dep(i, n - 1, -1) sa[-- cnt[px[i]]] = id[i];// 将rk[id[i]]存下来能减少不连续内存访问
        copy(all(rk), oldrk.begin());
        rk[sa[0]] = 0;
        p = 0;
        _rep(i, 1, n) rk[sa[i]] = cmp(sa[i - 1], sa[i], len) ? p : ++p; 
    }
    _rep(i, 0, n) cout << sa[i] << " \n"[i == n - 1];
    VI h(n);
    int k = 0;
    _rep(i, 0, n){
        int idx = rk[i];
        if(!idx) continue;
        int j = sa[idx - 1];
        while(i + k < n && j + k < n && s[i + k] == s[j + k]) k ++;
        h[idx] = k;
        k = max(k - 1, 0);
    }
    _rep(i, 0, n) cout << h[i] << " \n"[i == n - 1];
    return 0;
}