这份代码是《算法竞赛入门经典——训练指南》P221

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#define MAXN 100010
using namespace std;
char s[MAXN];
int sa[MAXN], rank[MAXN], height[MAXN];
int wa[MAXN], wb[MAXN], c[MAXN];
int n;

void Build_sa(int m)
{
    int i, *x=wa, *y=wb;
    for(i=0; i<m; i++) c[i] = 0;
    for(i=0; i<n; i++) c[x[i] = s[i]-'a']++;
    for(i=1; i<m; i++) c[i] += c[i-1];
    for(i=n-1; i>=0; i--) sa[--c[x[i]]] = i;
    for(int k=1; k<=n; k<<=1)
    {
        int p = 0;
        for(i=n-k; i<n; i++) y[p++] = i;
        for(i=0; i<n; i++) if(sa[i]>=k) y[p++] = sa[i]-k;
        for(i=0; i<m; i++) c[i] = 0;
        for(i=0; i<n; i++) c[x[y[i]]]++;
        for(i=1; i<m; i++) c[i] += c[i-1];
        for(i=n-1; i>=0; i--) sa[--c[x[y[i]]]] = y[i];
        swap(x,y);
        p = 1; x[sa[0]] = 0;
        for(i=1; i<n; i++)
            x[sa[i]] = (y[sa[i-1]]==y[sa[i]] && y[sa[i-1]+k]==y[sa[i]+k])?p-1:p++;
        m = p;
    }
}

void Build_height()
{
    int k = 0;
    for(int i=0; i<n; i++)
        if(rank[i] > 0)
        {
            if(k) k--;
            int j = sa[rank[i]-1];
            while(s[i+k]==s[j+k]) k++;
            height[rank[i]] = k;
        }
}

int main()
{
    scanf("%s", s);
    n = strlen(s);
    Build_sa(30);
    for(int i=0; i<n; i++) rank[sa[i]] = i;
    s[n] = '$';
    Build_height();
    for(int i=0; i<n; i++) printf("%d ",sa[i]+1); printf("\n");
    for(int i=1; i<n; i++) printf("%d ",height[i]); printf("\n");
    return 0;
}