后缀数组模板详解。

给定一个字符串S，比如它是（abcad）,那么它的后缀有”abcad“  ,"bcad ", "cad",  "ad", "d", ""。 讲这些后缀字符串按照字典序排序，得到的就是后缀数组。如果用普通的排序方法，排序要o（nlogn），但是每两个字符比较大小要O（n），所以是o（n × n log n）的复杂度。但是利用特殊的算法可以将其降到o（nlogn）。 给定一个字符串S，比如它是（abcad）,那么它的后缀有”abcad“  ,"bca