前情，字符串的字典序后缀排序
后缀倍增排序
定义：
字符串：连续的一段字符组成的串叫做字符串，更广义的，任何一个可比较大小的元素组成的数组都可称为字符串。
后缀：suffix(i) 表示字符串 s 从第 i 个位置开始的后缀，即由s[i]~s[n-1]组成的子串
比较：两个字符串大小的比较，从首位开始，一位一位按照 ASCII 进行比较，认为ASCII较小的字符串更小，如果一个字符串比较完了最后一位而另一个没有，则认为前者较小，如果两个字符串长度相同并且所有位置上的字符均相同，则认为两个字符串相等。
后缀数组：sa[] 是一个一维数组，保存了对字符串 s 的所有后缀排序后的结果。表示第 i 小的后缀在原串中的起始位置。
名次数组：rank[] 是一个一维数组，按起始位置保存了每个后缀在 sa[] 中的排名，rank[i]表示 suffix(i)的排名，是一个反向映射表，即 rank[sa[i]] = i 。
高度数组：height[] 是一个一维数组，保存了相邻两个后缀的最长公共前缀(Longest Common Prefix, LCP)长度。
倍增算法：暂时忽略
SA-IS算法：
SA-IS算法可以在线性时间内构造后缀序列
Pipeline：
1、对所有的后缀从右往左标注 S (smaller) 或 L (larger), 如果一个字母或后缀比他之前的更大则标注为 S ，更小或相等则标注为 L。
2、对于被标注为 S 的前缀，如果其后续字典序更大，则标注为 S* 。
3、将序列 A 分入buckets，buckets的长度取决于出现字符的频次，长度取决于字典序。
| Index | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| T | i | m | m | i | s | s | i | i | s | s | i | p | p | i | $ |
| Type | S | L | L | S* | L | L | S* | S | L | L | S* | L | L | L | S* |
| Buckets | $ | i | m | p | s | ||||||||||
4、将buckets进一步划分入 S- 和 L- buckets， L- buckets在S- buckets的前面。
| Index | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| T | i | m | m | i | s | s | i | i | s | s | i | p | p | i | $ |
| Type | S | L | L | S* | L | L | S* | S | L | L | S* | L | L | L | S* |
| Buckets | $ | i | m | p | s | ||||||||||
| Bucket-Typ | S | L | S | L | L | L | |||||||||
5、根据字典序排序 S* 后缀，并将其对应的填入 S- buckets。
5.1 对 S* 的子串进行诱导排序，使用大写字母进行表示，获得文本 T’
| Index | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| T’ | D | B | C | A |
| Place in T | 4 | 7 | 11 | 15 |
5.2 递归计算 A’
5.3 输出 A’ ，逆向转换得到排序，并顺序填入对应的Buckets-Typ
Index 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 T i m m i s s i i s s i p p i $ Type S L L
S* L L S* S L L S* L L L S* Buckets $ i m p s Bucket-Typ S L S L L L 15 7 11 4
6. 从左往右遍历 A ，如果在被标记为L，在对应的bucket的顺位中填充A[i] – 1,
7. 从右往左遍历，对对应的S Bucket从右往左填充
| Index | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| T | i | m | m | i | s | s | i | i | s | s | i | p | p | i | $ |
| Type | S | L | L | S* | L | L | S* | S | L | L | S* | L | L | L | S* |
| Buckets | $ | i | m | p | s | ||||||||||
| Bucket-Typ | S | L | S | L | L | L | |||||||||
| 15 | 7 | 11 | 4 | ||||||||||||
| 14 | 3 | 6 | 10 | ||||||||||||
| 2 | 13 | 5 | |||||||||||||
| 12 | 9 | ||||||||||||||
| 8 | |||||||||||||||
| 4 | |||||||||||||||
| 11 | |||||||||||||||
| 1 | |||||||||||||||
就。。。老实说吧，我没看懂
function SA-IS(S):
t = bool[]
S1 = int[]
P = int[]
bucket = int[]
扫描倒序字符串确定每一个后缀的类型 -> t
扫描t数组确定所有的LMS子串 -> P
对所有的LMS子串进行诱导排序
对每一个LMS子串重新命名，生成新的串S1
if S1中的每一个字符都不一样:
直接计算SA1
else
SA1 = SA-IS(S1) # 递归计算SA1
利用SA1来进行诱导排序，计算SA
return SA
后缀类型：对每一个后缀suffix(S, i)，当suffix(S,i)<suffix(S,i+1)时，是S型后缀。当suffix(S,i) >suffix(S,i+1)时，是L型后缀，对任意的$$i \in [0, \vert{S} -1]$$