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