后缀数组

后缀数组（Suffix Array）将字符串的所有后缀按字典序排列，配合 LCP（最长公共前缀）数组，可以高效解决大量字符串问题。

一、基本概念

graph TD
  A[字符串所有后缀] --> B[字典序排序]
  B --> C[sa[] + rank[]]
  C --> D[配合 height[] 解子串问题]

对字符串 s = "banana"，其后缀按字典序排列：

后缀        起始下标    排名
a           5          0
ana         3          1
anana       1          2
banana      0          3
na          4          4
nana        2          5

• sa[i]：排名第 i 的后缀的起始位置
• rank[i]：起始位置为 i 的后缀的排名
• height[i]：sa[i] 和 sa[i-1] 对应后缀的 LCP 长度

二、O(n log n) 构建（倍增法）

int[] buildSuffixArray(String s) {
    int n = s.length();
    int[] sa = new int[n], rank = new int[n], tmp = new int[n];

    // 初始：按单字符排序
    for (int i = 0; i < n; i++) { sa[i] = i; rank[i] = s.charAt(i); }

    for (int k = 1; k < n; k <<= 1) {
        int finalK = k;
        // 按 (rank[i], rank[i+k]) 排序
        Integer[] order = new Integer[n];
        for (int i = 0; i < n; i++) order[i] = i;
        Arrays.sort(order, (a, b) -> {
            if (rank[a] != rank[b]) return rank[a] - rank[b];
            int ra = a + finalK < n ? rank[a + finalK] : -1;
            int rb = b + finalK < n ? rank[b + finalK] : -1;
            return ra - rb;
        });
        for (int i = 0; i < n; i++) sa[i] = order[i];

        // 重新编号
        tmp[sa[0]] = 0;
        for (int i = 1; i < n; i++) {
            tmp[sa[i]] = tmp[sa[i-1]];
            if (rank[sa[i]] != rank[sa[i-1]] ||
                (sa[i]+k < n ? rank[sa[i]+k] : -1) != (sa[i-1]+k < n ? rank[sa[i-1]+k] : -1)) {
                tmp[sa[i]]++;
            }
        }
        int[] swap = rank; rank = tmp; tmp = swap;
        if (rank[sa[n-1]] == n - 1) break; // 所有排名不同
    }
    return sa;
}

三、Height 数组（LCP）

int[] buildHeight(String s, int[] sa) {
    int n = s.length();
    int[] rank = new int[n], height = new int[n];
    for (int i = 0; i < n; i++) rank[sa[i]] = i;

    int h = 0;
    for (int i = 0; i < n; i++) {
        if (rank[i] > 0) {
            int j = sa[rank[i] - 1];
            while (i + h < n && j + h < n && s.charAt(i+h) == s.charAt(j+h)) h++;
            height[rank[i]] = h;
            if (h > 0) h--;
        } else {
            h = 0;
        }
    }
    return height;
}

四、应用

1. 最长重复子串

= max(height[i])

2. 两个后缀的 LCP

= min(height[rank[i]+1], ..., height[rank[j]])（RMQ）

3. 模式匹配

二分 sa 数组 + 逐字符比较 → O(m log n)

4. 不同子串个数

= n(n+1)/2 - Σheight[i]

五、复杂度

六、后缀数组 vs 后缀自动机 vs Trie

七、面试要点

1. sa/rank/height 三数组：互相转换
2. 倍增排序：每轮按 (rank[i], rank[i+k]) 排
3. height 性质：LCP(sa[i], sa[j]) = min(height[i+1..j])
4. 不同子串：总子串数 - Σheight
5. LeetCode：1044（最长重复子串，可用 SA 或哈希）

八、倍增法构建过程模拟

以 s = "banana" 为例，演示倍增排序的每一轮：

后缀： banana, anana, nana, ana, na, a

第1轮（按前 1 个字符排序）：
  a(5) < ana(3) < anana(1) < banana(0) < na(4) < nana(2)
  rank = [b:1, a:0, n:2, a:0, n:2, a:0] → 按首字母分组

第2轮（按前 2 个字符，用 (rank[i], rank[i+1]) 作关键字）：
  a < an < an < ba < na < na

第4轮（按前 4 个字符）：
  a < ana < anan... 逐步细分

直到某一轮所有 rank 互不相同 → 排序完成

最终 sa = [5, 3, 1, 0, 4, 2]
  sa[0]=5 → "a"
  sa[1]=3 → "ana"
  sa[2]=1 → "anana"
  sa[3]=0 → "banana"
  sa[4]=4 → "na"
  sa[5]=2 → "nana"

height[i] = LCP(sa[i-1], sa[i])：
  height[2] = LCP("ana","anana") = 3
  height[5] = LCP("na","nana") = 2

为什么是 O(n log n)：每轮排序后“有效区分长度”翻倍，最多 log n 轮；每轮用基数排序 O(n)。

九、height 数组的妙用

性质：任意两个后缀的 LCP = 它们 rank 之间所有 height 的最小值
  LCP(sa[i], sa[j]) = min(height[i+1], ..., height[j])  (i < j)

应用1：最长重复子串 = max(height)
  banana 的 height 最大值 = 3（"ana" 出现两次）

应用2：不同子串个数 = n(n+1)/2 - Σheight[i]
  每个后缀贡献 n-sa[i] 个新子串，减去与前一后缀重复的 height[i] 个

十、思考题

1. 为什么倍增法每轮可以用基数排序而不是比较排序？这对复杂度有什么影响？（提示：关键字是整数 rank）
2. 求“最长重复子串”为什么等价于求 height 数组的最大值？（提示：重复子串 = 两个后缀的公共前缀）
3. 如果要求“至少出现 k 次的最长子串”，如何在 height 数组上求解？（提示：滑动窗口求长度≥k-1 的 height 区间最小值的最大值）

练习推荐：LC 1044 可用后缀数组或“二分+哈希”两种解法，建议先掌握 字符串哈希 再对比。