深入理解后缀数组（C语言实现详解：从零构建高效字符串处理利器）

为什么需要后缀数组？

后缀数组是许多高级字符串算法的基础。相比后缀树，它占用内存更少，且易于用数组实现。常见用途包括：

• 快速查找子串
• 计算最长公共前缀（LCP）
• 寻找重复子串
• 基因序列比对（生物信息学）

C语言实现后缀数组（暴力法）

对于初学者，我们可以先用最直观的方法：生成所有后缀，然后排序。虽然效率不高（时间复杂度 O(n² log n)），但逻辑清晰，便于理解。

以下是完整的 C 语言代码：

#include <stdio.h>#include <stdlib.h>#include <string.h>int compare_suffixes(const void* a, const void* b) {    int i = *(const int*)a;    int j = *(const int*)b;    char* str = (char*)global_str; // 注意：这里为了简化，使用全局变量    return strcmp(str + i, str + j);}char* global_str; // 全局字符串指针，供比较函数使用void build_suffix_array(char* str, int n, int* suffix_arr) {    // 初始化后缀数组：0, 1, 2, ..., n-1    for (int i = 0; i < n; i++) {        suffix_arr[i] = i;    }    global_str = str; // 设置全局字符串    // 使用 qsort 对后缀起始位置排序    qsort(suffix_arr, n, sizeof(int), compare_suffixes);}int main() {    char str[] = "banana";    int n = strlen(str);    int suffix_arr[n];    build_suffix_array(str, n, suffix_arr);    printf("后缀数组: ");    for (int i = 0; i < n; i++) {        printf("%d ", suffix_arr[i]);    }    printf("\n");    // 打印排序后的后缀（验证）    printf("排序后的后缀:\n");    for (int i = 0; i < n; i++) {        printf("%s\n", str + suffix_arr[i]);    }    return 0;}

这段代码使用了 C 标准库的 qsort 函数对后缀起始索引进行排序。注意：由于 qsort 的比较函数不能直接传入额外参数，我们使用了一个全局变量 global_str 来传递字符串地址（实际项目中建议使用更安全的方式，如封装结构体）。

优化方向：倍增算法（Manber-Myers）

上述暴力方法适用于小字符串，但对于大文本（如 DNA 序列）效率太低。工业级实现通常采用 O(n log n) 的倍增算法（也称 Manber-Myers 算法）。该算法通过逐步比较后缀的 1、2、4、8... 长度前缀来排序，避免了每次比较整个后缀。

虽然实现较复杂，但它是掌握高级C语言后缀数组技术的关键。感兴趣的同学可以在掌握基础后深入学习。

总结

通过本教程，你已经了解了：

• 后缀数组的定义与作用
• 如何用 C 语言实现一个简单的后缀数组
• 后缀数组在字符串算法中的重要地位

后缀数组是算法竞赛和系统开发中的实用工具。掌握它，你就离成为字符串处理高手又近了一步！

记住关键词：后缀数组、C语言后缀数组、字符串算法、后缀排序——它们是你深入学习的路标。