在本文中，我们探讨了一种新颖的数据结构——后缀数组（suffix array），它结合了对文本 $T$ 的直接访问索引，从而能够高效地处理多种模式匹配查询。
我们展示了如何在 $O(\frac{n\log \sigma}{\sqrt{\log n}}+\min(r,\bar{r})\log^\epsilon n)$ 时间内计算文本 $T[1\dots n]$ 的最小后缀数组，其中 $\sigma$ 是文本的字母表大小，$r$ 和 $\bar{r}$ 分别是 $T$ 及其反向文本 $\overline{T}$ 的 Burrows-Wheeler 变换中的相同字母序列的数量。
当 $\sigma$ 足够小且 $\min(r,\bar{r})=o(\frac{n}{\log^\epsilon n})$ 时，该时间复杂度可达到亚线性，这相较于当前最先进的算法有了显著的提升。此外，我们还呈现了一系列相关的算法结果。
博主点评： 本文提出的后缀数组结构为模式匹配问题提供了创新的解决方案，尤其在处理小字母表的情况下展现了显著的性能优势，值得在实际应用中进一步探索。