题解 | #Suffix Sort#

Suffix Sort

https://ac.nowcoder.com/acm/contest/33192/I

首先要想办法能快速判断两个字符串在最小表示法下的字典序大小，主要利用两点：

相同字符在最小表示法下的大小关系也是相同的；
对字典序大小关系”起决定性因素的“是第一个不同的字符

于是考虑把每个字符单独拆开看，先预处理出每个后缀 $S [i :]$ 从位置 $i$ 开始往后第一个出现、第二个出现的字符是什么。比较两个后缀 $S [i :]$ 和 $S [j :]$ 的字典序时，从小到大枚举第 $k$ 大(也就是第 $k$ 个出现的字符)，想办法匹配出第一个 ”不同构“(见下面图解) 的位置；最终所有 26 个字符第一个 ”不同构“ 的位置取最小值，就是两个后缀在最小表示法下第一个不同的字符位置，比较这个字符在两个后缀各自最小表示法中的大小即可判断字典序。

关于 “同构“ (从题解中借来的词qwq):
比如这两个字符串： $s = \text{abc abc bca},\ t = \text{xyz xyz xxy}$ (空格仅用作分隔，abc 和 xyz 的大小关系是相对应的)

alt

分别枚举这两个字符串第一个出现( a 和 x )，第二个 ( b 和 y )，第三个 ( c 和 z ) 的字符

找到第一个不相同的位置。至于怎么找，这里用每个字符和前一个同种字符的相对位置来找，比如说 a 和 x，第三个 a 和第二个 a 之间相差 $5$ ，而第三个 x 和第二个 x 之间相差 $3$ ；不过第一个位置要特判处理。

接下来就是题解中说的：对 26 个字符的位置的差分数组跑 sa，或者哈希，反正能求两个字符的位置下标的差分数组的任意两个后缀的 lcp 就行；枚举两个后缀第 $k$ 次出现的字符是什么，找到对应字符的差分数组的相对应的后缀，求 lcp 得到第一个不同的位置。最后取个最小值。

跑了 2600ms+ 的代码:

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int INF = 1e9 + 7;
const bool debug = false;

// -------- n * logn * logn 的倍增 sa --------
int s2[220010];
int sa[220010], lcp[220010], Rank[220010], temp[220010];
// cur_len 是当前倍增处理的子串长度，Length 是总长度
int Length, cur_len;
bool comp(int i,int j) {
    if( Rank[i] != Rank[j] )return Rank[i] < Rank[j];
    else{
        // 因为用 -1 分隔不同字符的位置差分数组,那末尾要用更小的 -2
        int ri = i + cur_len > Length ? -2 : Rank[i+cur_len];
        int rj = j + cur_len > Length ? -2 : Rank[j+cur_len];
        return ri < rj;
    }
}
void construct_sa(int len) {
    for(int i=0;i<=len;i++) {
        Rank[i] = (i==len ? -2 : s2[i]);
        sa[i] = i;
    }

    for( cur_len=1; cur_len<=len; cur_len*=2 ) {
        sort( sa,sa+len+1,comp );
        temp[sa[0]] = 0;
        for(int i=1;i<=len;i++) {
            temp[sa[i]] = temp[sa[i-1]] + comp(sa[i-1],sa[i]);
        }
        for(int i=0;i<=len;i++)Rank[i] = temp[i];
    }
}
void construct_lcp(int len) {
    for(int i=0;i<=len;i++) Rank[sa[i]] = i;
    int h=0;
    for(int i=0;i<len;i++) {
        if( h>0 ) h--;
        int j = sa[Rank[i]-1];
        for( ;j+h<len && i+h<len; h++ ){
            if( s2[i+h] != s2[j+h] )break;
        }
        lcp[ Rank[i]-1 ] = h;
    }
}
// ------------- sa 部分 -------------
// 高度数组的 st 表
int st[20][220010], lg[220010];
void construct_st(int n) {
    for(int i=1;i<=n;i++)st[0][i] = lcp[i];

    for(int k=1,len=2; len<=n; len*=2,k++) {
        for(int i=1;i+len-1<=n;i++) {
            st[k][i] = min( st[k-1][i], st[k-1][i+len/2] );
        }
    }
}
inline int query_min(int left,int right) {
    if( left > right ) swap(left,right);
    int k = lg[right-left];
    return min( st[k][left], st[k][right-(1<<k)] );
}

int n;
char s[220010];
int Next[220010][26];
vector<int> pos[26];
pair<int,int> Map[220010];
int Index[220010];
int ans[220010];

// 比较两个后缀 S[x:] 和 S[y:] 的字典序大小
// 无比杂乱的代码，各种位置下标的映射，当初 debug 一晚上才最终过掉
bool comp2(int x,int y) {
    // Min 用来记录第一个不同的字符到后缀起始位置的长度
    int Min = INF;
    for(int k=0; k<26; k++) {
        // 两个后缀各自第 k 个字符的第一次出现位置
        int nx = Next[x][k];
        int ny = Next[y][k];
        // 特判掉第一个位置
        if( nx-x != ny-y || nx > n || ny > n ) {
            Min = min( Min, min(nx-x,ny-y) );
            continue;
        }

        // 在原串 s 中下标为 nx 的字符是 ('a'+i1)，其位置在 pos[i1] 的下标是 j1
        auto& [i1,j1] = Map[nx];
        auto& [i2,j2] = Map[ny];

        int LCP;
        // 求从第二个位置往后的后缀的 lcp
        if( j1+1 == pos[i1].size() || j2+1 == pos[i2].size() ) LCP = 0;
        else {
            // Index 用来将原串的下标映射到跑后缀数组中的下标位置
            LCP = query_min( Rank[ Index[ pos[i1][j1+1] ] ], Rank[ Index[ pos[i2][j2+1] ] ] );
            // 与各自后缀的长度取最小值，即便每个字符的位置差分数组之间都用 -1 隔开, lcp也可能"误判"
            LCP = min( LCP, min( (int)(pos[i1].size()) - (j1+1), (int)(pos[i2].size()) - (j2+1) ) );
        }
        ++ LCP; // 加上第一个字符
        
        // 第一个不同的字符的位置在哪
        int difx = ( j1 + LCP >= pos[i1].size() ? n+1 : pos[i1][j1 + LCP] );
        int dify = ( j2 + LCP >= pos[i2].size() ? n+1 : pos[i2][j2 + LCP] );
        Min = min( Min, min( difx - x, dify - y ) );// 可见下面的图示 2-1
    }

    int rk1 = 27, rk2 = 27;
    for(int i=25; i>=0; i--) {
        // 第一个不同的字符在各自后缀中排第几
        if( s[Next[x][i]] == s[x + Min] ) rk1 = i;
        if( s[Next[y][i]] == s[y + Min] ) rk2 = i;
    }
    // 如果是字符串末尾要置为最小
    if( x + Min > n ) rk1 = -1;
    if( y + Min > n ) rk2 = -1;
    return rk1 < rk2;
}

void Print_sa() {
    for(int i=0;i<=Length;i++) {
        printf("%4d %4d %4d :",i,sa[i],lcp[i]);
        for(int j=sa[i]; j<Length; j++) printf(" %d",s2[j]);
        printf("\n");
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    for(int i=2;i<=210000;i++) lg[i] = lg[i>>1] + 1;
    
    cin >> n;
    cin >> (s+1);

    vector<int> last(26,n+1);
    for(int i=n; i>0; i--) {
        last[ s[i] - 'a' ] = i;
        for(int j=0;j<26;j++) Next[i][j] = last[j];
        // 排序之后, Next[i][j] -> 从位置 i 开始, 第 j 个出现的字符的下标
        sort( Next[i], Next[i] + 26 );
    }

    for(int i=1;i<=n;i++) {
        pos[ s[i] - 'a' ].push_back(i);
    }

    Length = 0;
    for(int i=0; i<26; i++) {
        int siz = pos[i].size();
        for(int j=0; j<siz; j++) {
            // 下标为 pos[i][j] 的字符 在 pos 哪个地方
            Map[ pos[i][j] ] = make_pair(i,j);
            // 下标的 pos[i][j] 在 s2 中的位置
            Index[ pos[i][j] ] = Length;

            s2[Length] = pos[i][j];
            ++ Length;
        }
        // -1 分隔,。 如果字符 ('a'+i) 没有出现过就不会连着两个 -1,
        if( Length > 0 && s2[Length-1] > 0 ) s2[Length++] = -1;
    }

    // 差分
    for(int i=Length-1; i>0; i--) {
        if( s2[i-1] > 0 && s2[i] > 0 ) s2[i] -= s2[i-1];
    }

    construct_sa(Length);
    construct_lcp(Length);
    construct_st(Length);

    for(int i=1;i<=n;i++) ans[i] = i;
    sort(ans + 1, ans + n + 1, comp2);

    for(int i=1;i<=n;i++) cout << ans[i] << ' ';
    
}

/*

aadead
a : 1 2 5
d : 3 6
e : 4

s2: 1 1 4 -1 3 3 -1 4 -1
   0    9    0 :
   1    8    1 : -1
   2    3    1 : -1 3 3 -1 4 -1
   3    6    0 : -1 4 -1
   4    0    1 : 1 1 4 -1 3 3 -1 4 -1
   5    1    0 : 1 4 -1 3 3 -1 4 -1
   6    5    1 : 3 -1 4 -1
   7    4    0 : 3 3 -1 4 -1
   8    7    2 : 4 -1
   9    2    0 : 4 -1 3 3 -1 4 -1

*/

alt