Burrows-Wheeler 变换（BWT）是一种通过对字符串进行循环旋转并按字典序排序生成的新序列，具有可逆性，能够仅凭最后一列恢复原始字符串。FM-index 是基于 BWT 的全文索引结构，支持在压缩空间内进行精确模式匹配。BWT 广泛应用于数据压缩（如 bzip2）和基因组比对（如 BWA），推动了二代测序技术的发展。

后缀数组是一种高效的字符串处理数据结构，由Udi Manber和Gene Myers于1993年提出，旨在降低后缀树的内存占用。后缀数组支持快速模式匹配和最长公共子串等操作，内存需求显著低于后缀树。SA-IS算法可在线性时间内构造后缀数组，结合LCP数组后可完全替代后缀树，广泛应用于基因组比对和全文搜索等领域。