P3809 后缀排序（模板）

理解的困难在于

for( lint k = 1;(1 << k) < n;k++ )

含义是前面一个 长度为 ( 1 << k ) 的串，后面一个长度 小于等于 ( 1 << k ) 的串拼起来。

这样拼成的最长串的长度为( 1 << (k+1) ) ( >= n 时循环跳出 )

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef int lint;
const lint maxn = 1000000 + 10;
char s[maxn];
struct suffix{
    lint c[maxn],sa[maxn],x[maxn],y[maxn],m,n;
    void init(){
        m = 0;
        c[0] = 0;
    }
    void Build_SA(){
        n =strlen(s);
        for( lint i = 0;i < n;i++ ) m = max( m,(lint)s[i] );
        for( lint i = 0;i < n;i++ ){
            x[i] = s[i];
            c[ s[i] ]++;
        }
        for( lint i = 1;i <= m;i++ ) c[i] += c[i-1];
        for( lint i = 0;i < n;i++ ) {
            sa[ --c[ x[i] ] ] = i;
        }
        for( lint k = 1;(1 << k) < n;k++ ){ 
            lint cnt = 0;
            for( lint i = n - k;i < n;i++ ) y[cnt++] = i; //这些位置长度小于等于 1 << k，无法由一个长度为k后面加上长度小于等于k的子串拼接而成，如果按照第二个子串进行排序，他的排序最小。
            for( lint i = 0;i < n;i++ ) if( sa[i] >= k ) y[cnt++] = sa[i]-k;
            for( lint i = 0;i <= m;i++ ) c[i] = 0;
            for( lint i = 0;i < n;i++ ) c[ x[i] ]++;
            for( lint i = 1;i <= m;i++ ) c[i] += c[i-1];
            for( lint i = cnt-1;i >= 0;i-- ) sa[ --c[ x[ y[i] ] ] ] = y[i];
            swap( x,y );
            lint num = 0;
            x[ sa[0] ] = 0;
            for( lint i = 1;i < n;i++ ){
                if( y[ sa[i-1] ] != y[ sa[i] ] || y[ sa[i-1]+k ] != y[ sa[i]+k ] ){
                    x[ sa[i] ] = ++num;
                }else{
                    x[ sa[i] ] = num;
                }
            }
            if( num == n-1 ) return;
            m = num;
        }
    }
}g;
int main()
{
    scanf("%s",s);
    g.init();
    g.Build_SA();
    for( lint i = 0;i < g.n;i++ ){
        printf("%d ", g.sa[i]+1 );
    }
    return 0;
}