深入理解后缀数组（C语言实现详解与字符串处理实战）

以 "banana" 为例，排序后的后缀顺序为：

1. a → 起始索引 5
2. ana → 起始索引 3
3. anana → 起始索引 1
4. banana → 起始索引 0
5. na → 起始索引 4
6. nana → 起始索引 2

因此，后缀数组为：[5, 3, 1, 0, 4, 2]。

为什么需要后缀数组？

相比暴力比较所有子串，后缀数组能将许多字符串操作的时间复杂度从 O(n²) 降低到 O(n log n) 甚至 O(n)。它是解决以下问题的关键工具：

• 最长公共前缀（LCP）
• 重复子串查找
• 字典序最小/最大循环移位

掌握C语言实现后缀数组是学习高级字符串算法的重要一步。

C语言实现后缀数组（基础版）

最直观的方法是生成所有后缀，然后使用标准库函数 qsort 进行排序。虽然效率不是最优（O(n² log n)），但逻辑清晰，适合初学者理解。

#include <stdio.h>#include <stdlib.h>#include <string.h>// 比较函数：用于 qsortint compare_suffixes(const void *a, const void *b) {    int i = *(const int*)a;    int j = *(const int*)b;    return strcmp(s + i, s + j); // s 是全局字符串}char s[1000]; // 全局字符串，便于 compare_suffixes 访问int main() {    printf("请输入一个字符串: ");    scanf("%s", s);    int n = strlen(s);        // 创建后缀起始索引数组    int *suffix_array = (int*)malloc(n * sizeof(int));    for (int i = 0; i < n; i++) {        suffix_array[i] = i;    }        // 排序后缀数组    qsort(suffix_array, n, sizeof(int), compare_suffixes);        // 输出结果    printf("后缀数组为: ");    for (int i = 0; i < n; i++) {        printf("%d ", suffix_array[i]);    }    printf("\n");        free(suffix_array);    return 0;}

⚠️ 注意：上面的代码使用了全局变量 s，这是为了简化 compare_suffixes 函数的编写。在实际项目中，建议通过结构体或额外参数传递字符串指针以提高代码可维护性。

更高效的实现：倍增算法（O(n log n)）

对于大型字符串（如基因组数据），基础版效率太低。工业级应用通常采用倍增算法（Doubling Algorithm）或 SA-IS 算法。这里我们简要介绍倍增思想：

1. 首先按第一个字符对后缀排序；
2. 然后按前两个字符排序；
3. 再按前四个字符排序……
4. 每次将排序长度翻倍，直到覆盖整个字符串。

该方法利用了上一轮的排序结果，避免重复比较，从而达到 O(n log n) 的时间复杂度。

总结

通过本教程，你已经了解了后缀数组的基本概念、应用场景，并学会了用 C 语言实现一个基础版本。虽然还有更高效的算法，但掌握这个入门实现是迈向高级字符串算法的关键一步。后续你可以尝试实现 LCP 数组，或研究 SA-IS 等线性时间算法。

记住，无论是文本处理还是生物信息学，C语言实现后缀数组都是提升程序性能的利器。动手写一写，你会对后缀排序有更深的理解！