后缀数组（Suffix Array）原理与实现

后缀数组是一种用于高效处理字符串的数据结构，特别适用于字符串匹配、最长公共子串等场景。它通过存储字符串的所有后缀的排序信息，来支持快速查询操作。

一、后缀数组的基本概念

• 给定一个长度为n的字符串S，其后缀数组SA是一个长度为n的数组，其中每个元素表示S的某个后缀的起始位置，且这些后缀按字典序排列。
• 例如，对于字符串S="banana"，其所有后缀为：
  • 起始位置0: "banana"
  • 起始位置1: "anana"
  • 起始位置2: "nana"
  • 起始位置3: "ana"
  • 起始位置4: "na"
  • 起始位置5: "a"
• 按字典序排序后得到后缀数组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"

二、后缀数组的构建方法

1. 朴素方法：
   • 生成所有后缀（O(n)个），直接排序（每个后缀比较最多O(n)次），总时间复杂度O(n² log n)，适用于短字符串。
2. 倍增算法（高效构建）：
   • 步骤：
     a. 初始化：对每个字符排序，得到初始排名（长度为1的子串）。
     b. 倍增：每次将排序长度加倍，利用前一次排序结果合并得到新排名。
     c. 重复直到所有后缀排名唯一。
   • 时间复杂度：O(n log n)，利用基数排序可优化至O(n log n)。

三、后缀数组的辅助结构：高度数组（LCP Array）

• 高度数组LCP记录相邻后缀的最长公共前缀长度。
• 例如，对SA=[5,3,1,0,4,2]：
  • LCP[0]无定义（通常设为0）
  • LCP[1]：比较"a"和"ana"的公共前缀长度为1
  • LCP[2]："ana"和"anana"的公共前缀长度为3
  • 以此类推。
• 构建方法：利用后缀数组的性质，通过线性扫描计算，时间复杂度O(n)。

四、后缀数组的应用

1. 字符串匹配：
   • 问题：在文本S中查找模式P。
   • 步骤：利用后缀数组的有序性，对P进行二分查找，比较时逐字符匹配。
   • 时间复杂度：O(m log n)，其中m为模式长度，n为文本长度。
2. 最长公共子串：
   • 问题：求多个字符串的最长公共子串。
   • 步骤：将字符串连接（用特殊字符分隔），构建后缀数组和高度数组，通过扫描高度数组找到跨所有字符串的公共前缀。
   • 时间复杂度：O(n log n)。

五、实现示例（倍增算法伪代码）

function build_suffix_array(S):
    n = len(S)
    SA = [0, 1, ..., n-1]  # 初始后缀数组
    rank = [ord(S[i]) for i in range(n)]  # 初始排名

    k = 1
    while k < n:
        # 按第一关键字（当前排名）和第二关键字（偏移k的排名）排序
        SA.sort(key=lambda i: (rank[i], rank[i+k] if i+k < n else -1))
        new_rank = [0] * n
        new_rank[SA[0]] = 0
        for i in range(1, n):
            # 若当前后缀与前一后缀关键字相同，则排名相同
            new_rank[SA[i]] = new_rank[SA[i-1]] + 1 if (rank[SA[i]] != rank[SA[i-1]] or (max(SA[i], SA[i-1]) + k < n and rank[SA[i]+k] != rank[SA[i-1]+k])) else new_rank[SA[i-1]]
        rank = new_rank
        k *= 2
    return SA

六、总结

• 后缀数组通过空间换时间（O(n)空间），支持高效的字符串查询。
• 结合高度数组可解决复杂字符串问题，如最长重复子串、最长回文子串等。
• 实际应用中需注意特殊字符处理（如末尾添加唯一最小字符）以保证正确性。