后缀数组

用倍增求得后缀数组, o(nlogn):

1. 求得后缀排名rk, 即排名的后缀sa

LL n;// 下标从1开始
char s[N];
int sa[N], rk[N], rk2[N], ht[N];

void getSa() {// 根据rk来倍增排序sa
    // initialized, 长度为1
    ltr(i, 1, n) { sa[i] = i, rk[i] = s[i]; }

    for (int k = 1; k <= n; k *= 2) {
        auto cmp = [&](int i, int j) {// 比较前一半和后一半
          if (rk[i] != rk[j])return rk[i] < rk[j];

          int r1 = (i + k <= n ? rk[i + k] : -1),
              r2 = (j + k <= n ? rk[j + k] : -1);
          return r1 < r2;
        };

        sort(sa + 1, sa + 1 + n, cmp);

        rk2[sa[1]] = 1;// 基数排序
        ltr(i, 1, n) rk2[sa[i]] = rk2[sa[i - 1]] + cmp(sa[i - 1], sa[i]);

        ltr(i, 1, n)rk[i] = rk2[i];
    }
}

void getHt() {
    ltr(i, 1, n)rk[sa[i]] = i;

    int k = 0;
    ltr(i, 1, n) {// 枚举排名第i-1和i名, 更新ht
        if (k)--k;// 去掉首字母, 重新比较

        int j = sa[rk[i] - 1];
        while (i + k <= n && j + k <= n && s[i + k] == s[j + k])++k;

        ht[rk[i]] = k;
    }
}

2. 可求得第k小子串

   CF128B string

// 每个后缀的前缀就是所有子串, 又后缀按照字典序作sa排序, 所以我们开a数组统计拓展, 直至ht, 以防重复
int a[N];// rk为i的后缀被提供(扩展)多少子串
//寻找第K小的子串
void findK(int k) {
    int curr = 1;
    while (k) {
        if (++a[curr] > n - sa[curr] + 1) {// 扩展当前后缀的前缀长度, 若超出, 则去到下一个后缀
            ++curr;
            continue;
        }
        --k;
        // 扫描并扩展包含当前相同子串, 扩展部分应小于lcp
        for (int i = curr + 1; i <= n && a[curr] <= ht[i] && k; ++i) {
            ++a[i], --k;
        }
    }
    ltr(i, 0, a[curr] - 1) {
        cout << s[sa[curr] + i];
    }
}