数据结构与算法_后缀数组

    在字符串的处理当中，后缀树和后缀数组都是非常有力的工具。其实后缀数组是后缀树的一个精巧的替代品，它比后缀树容易实现，能够实现后缀树的很多功能而时间复杂度也不太逊色，并且，它比后缀数组所占用的空间小很多。可以说，在信息学竞赛中后缀数组比后缀树要更为实用。

 1. 后缀数组的相关概念

    后缀： 后缀是指从某个位置 i 开始到整个串末尾结束的一个特殊子串。字符串 s 的从第 i 个字符开始的后缀表示为Suffix(i) ,也可以称为下标为 i 的后缀。

     例如：字符串 s = "aabaaaab" ，其后缀为， Suffix(0) = "aabaaaab", Suffix(1) = "abaaaab"

    后缀数组（Suffix Array）：后缀数组是指将所有后缀从小到大进行排序后，把排好序的后缀的下标 i 放入数组中，该数组称为后缀数组 SA。后缀数组记录的是下标。

    排名数组：是指下标为 i 的后缀排序后的名次。例如上面的例子，排序后的下标和名次，如图所示。rank[i] = num, 下标为 i 的后缀排序后的名次为 num。

    排名数组和后缀数组是可逆的，可以来回转换。

2. 后缀数组的构建思路

    因为倍增算法，每次比较的字符数翻倍，因此长度为 n 的字符串，最多需要 O(log n)排序，除了第一次排序外，后面的都是对二元组进行排序，如果采用快速排序，每次需要 O(log n) ，总时间复杂度为 O(nlog^2 n),而使用基数排序，每次时间复杂度为O(n),总时间复杂度为O(n log n)。因此采用基数排序实现。

3. 后缀数组的应用

1）最长重复子串

2）不同子串的个数