后缀数组的一种实现方法

在字符串处理当中，后缀树和后缀数组都是非常有力的工具，其中后缀树 大家了解得比较多，关于后缀数组则很少见于国内的资料。其实后缀数组是后 缀树的一个非常精巧的替代品，它比后缀树容易编程实现，能够实现后缀树的 很多功能而时间复杂度也不太逊色，并且，它比后缀树所占用的空间小很多。 可以说，在信息学竞赛中后缀数组比后缀树要更为实用。因此在本文中笔者想 介绍一下后缀数组的基本概念、构造方法，以及配合后缀数组的最长公共前缀 数组的构造方法，最后结合一些例子谈谈后缀数组的应用。