构建线性类型后缀

引言

在字符串处理算法中，后缀数组至关重要，因为它们为广泛的字符串相关问题提供了有效的解决方案。为了获得最佳结果，必须尽可能高效地构建后缀数组。SA-IS（基于感应排序的倾斜算法）是实现线性时间复杂度的知名算法。本文将介绍如何构建线性类型的后缀数组，并使用 C 语言实现它。

后缀数组是一种数据结构，用于表示给定字符串中每个后缀的字典序。创建后缀数组的第一步是根据字典序对后缀进行排序。像 SA-IS 这样的专用排序算法旨在实现线性时间复杂度，使其对于大型数据集非常有效。对于此任务，标准的排序算法如快速排序或归并排序将花费 O(n^2 * log n) 的时间。

SA-IS 算法

由 Ge Nong、Sen Zhang 和 Wai Hong Chan 创建的 SA-IS 算法具有线性时间复杂度，这是众所周知的。该算法基于感应排序，其主要思想是根据后缀的第一个字符对其进行排序，然后递归地对感应子串进行排序。

代码

输出

代码解释

头文件

• 代码包含动态内存分配 (stdlib.h)、标准输入/输出操作 (stdio.h) 和字符串操作 (string.h) 所需的头文件。

Suffix 结构

• 后缀由定义的 `struct Suffix` 表示。它有两个成员：`rank`，一个用于排序后缀的两个整数数组；以及 `index`，它表示后缀在原始字符串中的起始索引。

比较函数

• qsort 函数使用 `compareSuffixes` 函数作为比较函数，按字典序对后缀进行排序。对两个后缀的 `rank` 数组进行比较。

创建后缀数组函数

• 将输入字符串 `text` 及其长度 `n` 作为参数传递给 `buildSuffixArray` 函数。
• 输入字符串的后缀由初始化的 Suffix 结构数组表示。
• 使用 qsort 函数根据其秩对后缀进行排序。
• 后缀被排序，并且秩被迭代更新，直到获得最终的后缀数组，这构成了 SA-IS 算法的基础。

秩的初始化

• 输入字符串中的字符用于确定起始秩。Suffix 结构中的 rank 数组包含秩。

排序和排名

• 首先使用 qsort 函数对后缀进行排序。然后根据结果的字典序更新排名。

更新秩

• 迭代遍历后缀，循环根据它们的位置和其他后缀的连接修改它们的秩。

第二次排序阶段

• 更新秩后，还有一次排序阶段。为了实现线性时间复杂度，此阶段至关重要。

后缀数组输出

• 控制台显示最终的后缀数组。它按字典序显示输入字符串的后缀。

主函数

• main 函数使用了示例字符串 "banana"，并使用 strlen 来确定其长度。
• 将输入字符串及其长度传递给 buildSuffixArray 函数。

打印的输出

后缀数组显示在最终打印到控制台的结果中。