后缀数组初步

——《高级数据结构》
1991年，首次提出了后缀数组（suffix array）的概念。当时，这篇文章是为了提出一种新的数据结构，从而在处理"在线字符串查询"任务中相比较后缀树而言，能够更节省空间（只需要后缀树的1/5-1/3空间）。可见，后缀数组主要是作为后缀树的一个精简的替代品。在接下来的内容中我们将看到，后缀数组不仅仅具有节省空间的优势，而且比后缀树更容易实现，并且同样在许多字符串处理问题上有者不俗的表现。关于后缀数组的研究中不仅有优化构造复杂度的，还有一些关于压缩后缀数组以积极应用到数据压缩中的，另外还有一些关于维护字符串动态修改的研究。可见，在该领域中，后缀数组同样有着极其重要的作用。
下面，首先介绍后缀数组以及一些常见的构建方法，接着会引入最长公共前缀（LCP）对其扩展，并介绍一些常见的应用场景，最后通过一些例题和练习巩固所学内容。