后缀数组是处理字符串的有力工具。后缀数组是后缀树的一个非常精巧的 替代品，它比后缀树容易编程实现，能够实现后缀树的很多功能而时间复杂度也 并不逊色，而且它比后缀树所占用的内存空间小很多。可以说，在信息学竞赛中 后缀数组比后缀树要更为实用。本文分两部分。第一部分介绍两种构造后缀数组 的方法，重点介绍如何用简洁高效的代码实现，并对两种算法进行了比较。第二 部分介绍后缀数组在各种类型题目中的具体应用。-Suffix array is a powerful tool for deal