代码

//上一份代码是假的
#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N=1e6+11;

int x[N << 1], y[N << 1], sum[N], sa[N], ht[N];
char str[N];
void get_sa_ht(int len) {
    int m=133;
    for (int i = 0; i <= m; ++i) sum[i] = 0;
    for (int i = 1; i <= len; ++i) ++sum[x[i] = (int)str[i]];
    for (int i = 1; i <= m; ++i) sum[i] += sum[i - 1];
    for (int i = len; i ; --i) sa[sum[x[i]]--] = i;
    for (int h = 1; h <= len; h <<= 1) {
        int yt = 0;
        for(int i = len -h + 1; i <= len; ++i) y[++yt] = i;
        for(int i = 1;i <= len; ++i) {
            if(sa[i] - h > 0) {
                y[++yt] = sa[i] - h;
            }
        }
        for(int i = 0; i <= m; ++i) sum[i] = 0;
        for(int i = 1; i <=len; ++i) ++sum[x[i]];
        for(int i = 1; i <= m; ++i) sum[i] += sum[i - 1];
        for(int i = len; i; --i) sa[sum[x[y[i]]]--] = y[i];
        for(int i = 0; i <= len; ++i) y[i] = x[i];
        x[sa[1]] = 1;
        m=1;
        for(int i = 2; i <= len; ++i){
            if(y[sa[i]] == y[sa[i - 1]] && y[sa[i] + h] == y[sa[i - 1] + h])x[sa[i]] = m;
            else x[sa[i]] = ++m;
        }
        if(m == len)break;
    }
    for(int i = 1; i <= len ; ++i) {
        if(x[i] == 1)continue;
        ht[x[i]] = 0;
        if(i != 1 && ht[x[i - 1]] > 1)ht[x[i]] = ht[x[i - 1]] - 1;
        while(str[i + ht[x[i]]] == str[sa[x[i] - 1] + ht[x[i]]] && max(i + ht[x[i]], sa[x[i] - 1] + ht[x[i]]) <= len) ++ht[x[i]];
    }
}
int main() {
    scanf("%s", str + 1);
    int len = strlen(str + 1);
    get_sa_ht(len);
    for(int i = 1; i <= len; ++i) {
        printf("%d ", sa[i]);
    }
    printf("\n");
    for(int i = 2; i <= len; ++i) {
        printf("%d ",ht[i]);
    }
    return 0;
}

评测结果