-
基数排序
算法思想：利用桶的单调性，从低到高位依次将整数放进对应数位的桶中。
时间复杂度：\(O(d*(n+siz))\)，其中 \(d\) 为数位，\(n\) 为元素个数，\(siz\) 为桶的大小。 -
后缀树
对于字符串 \(s\)，取出 \(s\) 所有的后缀字串，并建立字典树。这个树就是 \(s\) 的后缀树。空间复杂度 \(O(N^2)\)。 -
后缀数组 SA
对于字符串 \(s\)，定义sa[i]表示 \(s\) 的 \(n\) 个后缀按字典序排序后的第 \(i\) 个后缀在 \(s\) 中的下标，其中 \(i\) 从 \(0\) 开始。 -
后缀数组的实现
直接使用 sort 排序，由于字符串的比较是 \(O(n)\) 的，总时间复杂度 \(O(n^2\times \log n)\)。
倍增求 sa[]。
- 将 \(s\) 中的字母按照字典序从 \(1\) 开始分配整数。
- 倍增拼接连续 \(1,2,4,...,\log n\) 的整数来代表每个后缀的排名，当拼接的数字互不相同时即停止，由得到的数字
sort即可确定字典序。
最坏复杂度 \(O(n\log^2 n)\)
拼数的时候可以每次重新编号，长度控制在两位数。 - 利用基数排序的优化
拿基数排序替换快排。d=2，所以跑的很快。
rnk[i] 表示以下标 \(i\) 开头的后缀在排序后的排名。
易知 sa[rnk[i]]=i;rnk[sa[i]]=i;。