洛谷-P3809-后缀排序（后缀数组）

#include "bits/stdc++.h"
using namespace std;
const int MAXN = 1e6 + 5;
char s[MAXN];
int sa[MAXN], rk[MAXN], height[MAXN];
void getSa(char* s, int* sa, int n, int m) {
    int* x = (int*)calloc(MAXN, sizeof(int));
    int* y = (int*)calloc(MAXN, sizeof(int));
    int* cnt = (int*)calloc(MAXN, sizeof(int));
    for (int i = 1; i <= n; i++) {
        cnt[x[i] = s[i]]++;
    }
    for (int i = 2; i <= m; i++) {
        cnt[i] += cnt[i - 1];
    }
    for (int i = n; i; i--) {
        sa[cnt[x[i]]--] = i;
    }
    for (int j = 1; j < n; j <<= 1) {
        int num = 0;
        for (int i = n - j + 1; i <= n; i++) {
            y[++num] = i;
        }
        for (int i = 1; i <= n; i++) {
            if (sa[i] > j) {
                y[++num] = sa[i] - j;
            }
        }
        for (int i = 1; i <= m; i++) {
            cnt[i] = 0;
        }
        for (int i = 1; i <= n; i++) {
            cnt[x[i]]++;
        }
        for (int i = 2; i <= m; i++) {
            cnt[i] += cnt[i - 1];
        }
        for (int i = n; i; i--) {
            sa[cnt[x[y[i]]]--] = y[i];
        }
        swap(x, y);
        x[sa[1]] = num = 1;
        for (int i = 2; i <= n; i++) {
            if (y[sa[i]] != y[sa[i - 1]] || y[sa[i] + j] != y[sa[i - 1] + j]) {
                x[sa[i]] = ++num;
            } else {
                x[sa[i]] = num;
            }
        }
        if (num >= n) {
            break;
        }
        m = num;
    }
    free(x);
    free(y);
    free(cnt);
}
void getHeight(char* s, int* sa, int* rk, int* height, int n) {
    for (int i = 1; i <= n; i++) {
        rk[sa[i]] = i;
    }
    int k = 0;
    for (int i = 1; i <= n; i++) {
        k = k != 0 ? k - 1 : k;
        int j = sa[rk[i] - 1];
        while (s[i + k] == s[j + k]) {
            k++;
        }
        height[rk[i]] = k;
    }
}
int main() {
    gets(s + 1);
    int len = strlen(s + 1);
    getSa(s, sa, len, 130);
    // getHeight(s, sa, rk, height, len);
    for (int i = 1; i < len; i++) {
        printf("%d ", sa[i]);
    }
    printf("%d\n", sa[len]);
    /*
    for (int i = 1; i < len; i++) {
        printf("%d ", rk[i]);
    }
    printf("%d\n", rk[len]);
    for (int i = 1; i < len; i++) {
        printf("%d ", height[i]);
    }
    printf("%d\n", height[len]);
    */
    return 0;
}