后缀数组

后缀数组是一种用于字符串处理的强大数据结构。它是一个整数数组，存储了一个字符串的所有后缀的字典序排序。后缀数组在许多字符串处理问题中都有应用，比如字符串匹配、最长公共前缀、重复子串查找等。

定义

给定一个字符串 S，其长度为 n。后缀数组 SA 是一个长度为 n 的数组，其中 SA[i] 表示字符串 S 的第 i 小的后缀在 S 中的起始位置。

例如，考虑字符串 S = "banana"，其后缀数组为 [5, 3, 1, 0, 4, 2]。这表示：

S[5:] = "a" 是字典序最小的后缀
S[3:] = "ana" 是第二小的后缀
S[1:] = "anana" 是第三小的后缀
依此类推

构建后缀数组

构建后缀数组的常用方法有多种，其中最经典的是基于倍增的算法，时间复杂度为 O(n log n)。以下是该算法的基本步骤：

初始化：将每个字符视为一个长度为 1 的后缀，按字典序排序。
倍增：将后缀的长度从 1 增加到 2、4、8，直到覆盖整个字符串。
在每一步中，根据当前长度的后缀排序结果，更新下一个长度的排序。

示例代码

以下是一个简单的 Python 示例代码，展示如何构建后缀数组：

def build_suffix_array(s):
    n = len(s)
    suffixes = [(s[i:], i) for i in range(n)]
    suffixes.sort()  # 按字典序排序
    suffix_array = [suffix[1] for suffix in suffixes]
    return suffix_array

# 示例
s = "banana"
suffix_array = build_suffix_array(s)
print("后缀数组:", suffix_array)

应用

字符串匹配：后缀数组可以用于快速查找一个模式在文本中出现的位置。
最长公共前缀：通过后缀数组，可以高效地计算两个后缀的最长公共前缀。
重复子串查找：后缀数组可以帮助找到字符串中最长的重复子串。

例子

假设我们有字符串 S = "banana"，其后缀数组为 [5, 3, 1, 0, 4, 2]。我们可以使用后缀数组来解决以下问题：

查找模式 "ana"：通过二分查找在后缀数组中找到模式的起始位置。
计算最长公共前缀：通过后缀数组和 LCP（Longest Common Prefix）数组，可以快速找到最长公共前缀。

结论

后缀数组是一个强大且高效的数据结构，适用于多种字符串处理问题。理解和掌握后缀数组的构建和应用，可以极大地提高解决字符串问题的能力。