1。后缀排序的直接应用
Burrows-Wheers变换是一种在数据压缩过程中使用的算法。对于长度为n的字符串T=t0t1t2t3…tn-1，令循环后缀Rotation(i)=titi+1…tn-1t0t1…ti-1，即，如果将T看做一个环状字符串，那么Rotation(i)将是从原第i个字符顺次读得的字符串。现在的问题是，对于集合R={Rotation(i)|i属于[0,n)}，将R中的字符串按照升序排序得到的字符串序列：Rotation(k0),Rotation(k1),…,Rotation(kn-1),其中Rotation(ki)<Rotation(ki+1)。求顺次取每个循环后缀最后一个字符得到的字符串，即求S=Rotation(k0)[n-1]Rotation(k1)[n-1]…Rotation(kn-1)[n-1].
后缀数组实现：如果不是循环后缀而只是简单的后缀，那么就是经典的后缀排序问题了。不过，这里同样可以用后缀数组构建算法中的后缀排序来解决。
我们拿倍增算法举例：当前计算T[0,n)的2p次方的后缀数组时，为了比较Ti的2p次方和Tj的2p次方，需要知道Ti的p次方和Ti+p的p次方，Tj+p的p次方。如果i+p>=n，在此问题中，将令Ti+p的p次方=T(i+p)%n的p次方，其余不变。不难发现，这样可以在O(n*log2n）的时间内解决该问题。
对循环后缀进行排序还有一些其他的应用。比如为了表示一些循环等价的字符串，基于最小表示法，可以用最小循环后缀来表示。

找到一个视频链接：
https://v.youku.com/v_show/id_XMjM3ODA0Njg0NA==.html

2多模式串的匹配
问题是：给定长度分别为m和n的模式串P和待匹配串T，询问P在T中出现的情况。
这是KMP算法可以处理的经典场景。那么后缀数组在这方面有什么优势呢？和后缀树一样，如果是待匹配串T不变，而有多次不同模式串的查询，KMP算法每次需要对模式串构建其自匹配数组，而后缀数组可以在只构建串T的后缀数组的情况下查询。
后缀数组实现:不难观察到，如果P中出现在T中，那么一定是作为某个后缀的前缀出现的，即P=Suffix(i)的m次方，其中i属于[0,n)。由于后缀数组中后缀的有序性，可以利用二分查找来找寻这样的位置i。假设当前正在比较P和Suffix（SA[mid]）的关系，我们从Suffix(SA[mid])的第一个字符开始依次与P进行比较。如果发现P是Suffix(SA[mid])的前缀，那么算法结束，否则，如果P小于Suffix（SA[mid]），显然查询区间就到了[Left，mid)，否则将在（mid,Right]里继续。
伪代码：
***tionFind§
{
Left<-0
Right<-n-1
While(Left<=Right) do
{
mid<-(Left+Right)/2
If (IsPrefix(P,Suffix(SA[mid])))
Then return SA[mid]
End If
If (P<Suffix(SA[mid]))
Then Right=mid-1
Else Left=mid+1
End If
End While
}
return -1}
接下来我们将到如何引入LCP来优化
回顾上文的内容，通过计算height数组和RMQ预处理，可以在O(1)的时间内，明天得到任意两个后缀SA[i]和SA[j]的最长公共前缀LCP_Idx(i,j)。本节我们将看到后缀数组如何通过LCP的引入获得更为广泛的字符串问题处理能力。
//接下去看不懂辽，就这样趴（今天晚上被一个平板模式搞到崩溃），明日再战