// 比较两个后缀i和j，先比较rank[i]和rank[j]（第一关键字），
// 若相等，再比较rank[i+k]和rank[j+k]（第二关键字）
bool cmp(int i, int j) {
    if (rank[i] != rank[j]) return rank[i] < rank[j];
    int ri = i + k < n ? rank[i + k] : -1;   // 如果i+k超出范围，设为-1（比任何排名都小）
    int rj = j + k < n ? rank[j + k] : -1;
    return ri < rj;
}

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstring>

using namespace std;

const int MAXN = 200010;

int sa[MAXN];      // 后缀数组
int rank[MAXN];    // 当前排名（每次迭代更新）
int tmp[MAXN];     // 临时排名
int k, n;          // k：当前比较长度；n：字符串长度

// 比较函数，用于std::sort
bool cmp(int i, int j) {
    if (rank[i] != rank[j]) return rank[i] < rank[j];
    int ri = i + k < n ? rank[i + k] : -1;   // 如果i+k超出范围，用-1
    int rj = j + k < n ? rank[j + k] : -1;
    return ri < rj;
}

void buildSA(const string &s) {
    n = s.size();
    // 初始化：每个后缀的排名就是它的第一个字符的ASCII值
    for (int i = 0; i < n; i++) rank[i] = s[i];
    
    // 倍增循环，k表示当前比较长度的半长（实际比较2k个字符？注意下文）
    // 初识k=1，比较前1个字符已经完成（rank已初始化）。然后每次k*=2，比较前2k个字符。
    // 为方便，代码中k表示当前已经比较的长度，每次循环用k作为偏移。
    for (k = 1; k < n; k *= 2) {
        // 准备排序：把所有后缀的索引放入sa
        for (int i = 0; i < n; i++) sa[i] = i;
        // 排序
        sort(sa, sa + n, cmp);
        // 重新计算排名：将排序结果中相等的后缀赋予相同排名
        tmp[sa[0]] = 0;
        for (int i = 1; i < n; i++) {
            // 如果sa[i-1]和sa[i]比较结果不相等（即cmp返回true），则排名递增
            tmp[sa[i]] = tmp[sa[i-1]] + (cmp(sa[i-1], sa[i]) ? 1 : 0);
        }
        // 将临时排名复制回rank
        for (int i = 0; i < n; i++) rank[i] = tmp[i];
        
        // 如果最大排名等于n-1，说明所有后缀都已区分开，提前结束
        if (rank[sa[n-1]] == n-1) break;
    }
}

int main() {
    string s = "banana";           // 测试字符串
    buildSA(s);
    
    cout << "后缀数组 (起始索引): ";
    for (int i = 0; i < n; i++) cout << sa[i] << " ";
    cout << endl;
    
    cout << "排序后的后缀:" << endl;
    for (int i = 0; i < n; i++) {
        cout << s.substr(sa[i]) << endl;
    }
    return 0;
}

def build_sa(s):
    n = len(s)
    # 初始排名：每个字符的ASCII码
    rank = [ord(c) for c in s]
    k = 1
    sa = list(range(n))          # sa初始为所有索引
    
    while True:
        # 按二元组 (rank[i], rank[i+k]) 排序
        sa.sort(key=lambda x: (rank[x], rank[x + k] if x + k < n else -1))
        
        # 计算新排名
        new_rank = [0] * n
        new_rank[sa[0]] = 0
        for i in range(1, n):
            prev, cur = sa[i-1], sa[i]
            prev_key = (rank[prev], rank[prev + k] if prev + k < n else -1)
            cur_key = (rank[cur], rank[cur + k] if cur + k < n else -1)
            new_rank[cur] = new_rank[prev] + (1 if prev_key != cur_key else 0)
        rank = new_rank
        
        if rank[sa[-1]] == n - 1:   # 所有排名都不同
            break
        k *= 2
    
    return sa

# 测试
s = "banana"
sa = build_sa(s)
print("后缀数组:", sa)
print("排序后的后缀:")
for idx in sa:
    print(s[idx:])

s = "mississippi"
后缀数组结果（起始索引）：[4, 3, 6, 2, 5, 1, 0, 9, 8, 7, 10]
排序后的后缀：
i           (4)
ippi        (3)
issippi     (6)
ississippi  (2)
mississippi (0)
pi          (9)
ppi         (8)
sippi       (7)
sissippi    (1)
ssippi      (10? 注意n=11，索引10是 'i'? 实际是 "i"? 等等需要验证，这里只是演示)