在近期的研究中，后缀数组（Suffix arrays）作为一种新型数据结构备受关注，因为它们提供了在空间复杂度上比传统的Run-Length BWT更优的模式匹配功能。现有多种算法可用于从后缀数组数据结构构建后缀集。我们提出了第一个满足以下条件的构建算法：(i) 线性时间复杂度，(ii) 单遍历结构，(iii) 可实际应用。这一特性使得该算法在处理大型文本集合时尤为有用。
我们通过实证展示了该算法在空间/时间权衡图中的优势，表明其在实际应用中的优越性。
博主点评： 本文提出的线性时间算法为后缀数组的构建提供了新的思路，尤其在处理大型数据集时显著提高了效率，具有重要的应用价值。