一、后缀数组是个啥玩意儿？
咱们先来打个比方。想象你有一本超级厚的字典，里面收录了某个语言的所有单词。现在有人问你："能不能快速找到所有以'ing'结尾的单词？"这时候，如果你把字典里的每个单词都倒着排（比如"running"变成"gninnur"），然后按字母顺序整理好，找起来就会特别快。后缀数组其实就是这么个思路，只不过它处理的是字符串的所有可能后缀。
举个具体例子，假设我们有个字符串"banana"，它的所有后缀是：
- banana
- anana
- nana
- ana
- na
- a
把这些后缀按字典序排序后得到：
- a
- ana
- anana
- banana
- na
- nana
对应的在原字符串中的起始位置就是[5,3,1,0,4,2]，这个位置数组就是所谓的"后缀数组"。
二、怎么构造这个神奇的后缀数组？
构造后缀数组有很多方法，咱们重点说说最实用的"倍增算法"。这个算法的妙处在于它像叠罗汉一样，一层层把比较的范围扩大。
来看个Java实现的例子：
import java.util.Arrays;
public class SuffixArray {
// 构建后缀数组的主方法
public static int[] buildSuffixArray(String text) {
int n = text.length();
Suffix[] suffixes = new Suffix[n];
// 初始化，先按单个字符排序
for (int i = 0; i < n; i++) {
suffixes[i] = new Suffix(i, text.charAt(i) - 'a',
(i+1 < n) ? (text.charAt(i+1) - 'a') : -1);
}
// 按第一个和第二个字符排序
Arrays.sort(suffixes);
// 开始倍增过程
for (int k = 4; k < 2*n; k *= 2) {
// 给每个后缀分配新的排名
int[] rank = new int[n];
int prevRank = suffixes[0].rank[0];
suffixes[0].rank[0] = 0;
rank[suffixes[0].index] = 0;
for (int i = 1; i < n; i++) {
// 如果当前后缀和前一个后缀的rank对相同，则分配相同的新rank
if (suffixes[i].rank[0] == prevRank &&
suffixes[i].rank[1] == suffixes[i-1].rank[1]) {
prevRank = suffixes[i].rank[0];
suffixes[i].rank[0] = suffixes[i-1].rank[0];
} else {
prevRank = suffixes[i].rank[0];
suffixes[i].rank[0] = i;
}
rank[suffixes[i].index] = suffixes[i].rank[0];
}
// 更新第二个rank
for (int i = 0; i < n; i++) {
int nextIndex = suffixes[i].index + k/2;
suffixes[i].rank[1] = (nextIndex < n) ? rank[nextIndex] : -1;
}
// 再次排序
Arrays.sort(suffixes);
}
// 提取最终的后缀数组
int[] suffixArr = new int[n];
for (int i = 0; i < n; i++) {
suffixArr[i] = suffixes[i].index;
}
return suffixArr;
}
// 后缀辅助类
static class Suffix implements Comparable<Suffix> {
int index; // 后缀起始位置
int[] rank = new int[2]; // 当前和后一个字符的排名
public Suffix(int index, int rank1, int rank2) {
this.index = index;
this.rank[0] = rank1;
this.rank[1] = rank2;
}
@Override
public int compareTo(Suffix other) {
return (this.rank[0] == other.rank[0]) ?
(this.rank[1] - other.rank[1]) :
(this.rank[0] - other.rank[0]);
}
}
public static void main(String[] args) {
String text = "banana";
int[] suffixArr = buildSuffixArray(text);
System.out.println("后缀数组为: " + Arrays.toString(suffixArr));
// 输出: [5, 3, 1, 0, 4, 2]
}
}
这个实现虽然看起来有点长，但其实核心思想很简单：先按单个字符排序，然后逐步扩大比较范围（2个字符、4个字符...），直到覆盖整个字符串。每次排序后，我们给每个后缀分配新的排名，这样下次排序时就可以利用之前的结果。
三、用后缀数组玩转字符串匹配
有了后缀数组，字符串匹配就变得特别高效。因为所有后缀都是排好序的，我们可以用二分查找来快速定位。
来看个实际应用的例子，我们要在文本中查找模式串：
import java.util.Arrays;
public class SuffixArraySearch {
// 在文本中搜索模式串
public static void search(String text, String pattern, int[] suffixArr) {
int n = text.length();
int m = pattern.length();
// 使用二分查找
int left = 0, right = n - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
// 获取当前后缀
String suffix = text.substring(suffixArr[mid], Math.min(suffixArr[mid] + m, n));
int cmp = pattern.compareTo(suffix);
if (cmp == 0) {
// 找到匹配
System.out.println("模式串出现在位置: " + suffixArr[mid]);
// 检查左边是否还有相同匹配
int temp = mid - 1;
while (temp >= 0 && text.substring(suffixArr[temp], Math.min(suffixArr[temp] + m, n)).equals(pattern)) {
System.out.println("模式串出现在位置: " + suffixArr[temp]);
temp--;
}
// 检查右边是否还有相同匹配
temp = mid + 1;
while (temp < n && text.substring(suffixArr[temp], Math.min(suffixArr[temp] + m, n)).equals(pattern)) {
System.out.println("模式串出现在位置: " + suffixArr[temp]);
temp++;
}
return;
} else if (cmp < 0) {
right = mid - 1;
} else {
left = mid + 1;
}
}
System.out.println("模式串未找到");
}
public static void main(String[] args) {
String text = "banana";
int[] suffixArr = SuffixArray.buildSuffixArray(text);
System.out.println("在后缀数组中搜索:");
search(text, "ana", suffixArr); // 会找到位置1和3
search(text, "nan", suffixArr); // 会找到位置2
search(text, "xyz", suffixArr); // 未找到
}
}
这个搜索算法的精妙之处在于它利用了后缀数组的有序性。每次比较都能排除掉一半的可能性，所以时间复杂度是O(m log n)，其中m是模式串长度，n是文本长度。这比暴力匹配的O(mn)快多了！
四、后缀数组的七十二变
后缀数组不光能用来搜索字符串，还有很多其他妙用：
- 最长重复子串：在后缀数组中，相邻的两个后缀的最长公共前缀就是重复的子串。
public static String longestRepeatedSubstring(String text) {
int n = text.length();
int[] suffixArr = SuffixArray.buildSuffixArray(text);
int maxLen = 0;
int startIndex = 0;
for (int i = 1; i < n; i++) {
int lcp = computeLCP(text, suffixArr[i-1], suffixArr[i]);
if (lcp > maxLen) {
maxLen = lcp;
startIndex = suffixArr[i];
}
}
return maxLen > 0 ? text.substring(startIndex, startIndex + maxLen) : "";
}
private static int computeLCP(String text, int i, int j) {
int lcp = 0;
while (i < text.length() && j < text.length() && text.charAt(i) == text.charAt(j)) {
i++;
j++;
lcp++;
}
return lcp;
}
构建BWT变换：Burrows-Wheeler变换是数据压缩的重要技术，后缀数组可以高效实现它。
基因组比对：在生物信息学中，处理DNA序列时后缀数组大显身手。
五、后缀数组的优缺点分析
优点：
- 空间效率高：相比后缀树，后缀数组只需要存储原始字符串和一个整数数组。
- 搜索高效：支持O(m log n)时间复杂度的模式匹配。
- 实现相对简单：特别是有了高效的排序算法后。
缺点：
- 构建复杂度：虽然倍增算法是O(n log n)，但对于超大文本仍然可能较慢。
- 更新困难：如果文本经常变化，维护后缀数组会比较麻烦。
- 需要额外结构：要实现更高级的功能，通常需要配合LCP（最长公共前缀）数组。
六、使用场景推荐
- 静态文本搜索：比如搜索引擎的索引构建，文档检索系统。
- 生物信息学：DNA序列分析，蛋白质序列比对。
- 数据压缩：BWT变换的基础。
- 拼写检查：快速查找相似单词。
- 抄袭检测：查找文档中的重复段落。
七、注意事项
- 对于Unicode文本，需要特别注意字符编码问题。
- 内存消耗要考虑，特别是处理超大文本时。
- 如果只需要简单搜索，可以考虑更简单的算法如KMP。
- 实际应用中，通常会配合其他数据结构如LCP数组一起使用。
八、总结
后缀数组就像字符串处理中的瑞士军刀，虽然学习曲线有点陡峭，但一旦掌握，就能解决很多棘手的问题。从构建到应用，整个过程体现了算法设计的精妙之处。下次当你遇到字符串处理难题时，不妨想想后缀数组这把利器！
评论