WIKI

后缀数组

后缀

后缀是指从某个位置i 开始 到整个串末尾结束的一个特殊子串

字符串S的从i开头的后缀 表示为 Suffix(S,i) 也就是 Suffix(S,i)=S[i……len(S)]

后缀数组

后缀数组SA 是一个一维数组 保证 SA[i]<SA[i+1] 1≤i<n

也就是将 S 的 n 个后缀排序后放到数组中

名次数组

名次数组 Rank = 1/SA

若SA[i]=j 则 Rank[j]=i

也就是 名次数组Rank保存的是一个后缀的名次

如何构造后缀数组

直观的想法是O(n) 枚举所有后缀 然后 O(nlogn) 排序

这样的时间复杂度是O(n^2logn) 的

并没有利用后缀之间的关系

下面我们介绍O(nlogn) 的倍增算法

对于字符串u 我们定义 u 的k- 前缀
$$ u^k = \begin{cases} u[1\dots k] & \text{if }len(u)\ge k ,\\ u & \text{if } len(u) <k. \end{cases} $$

我们定义 k- 前缀比较关系 $<_k,=_k和\le_k :$

设两个字符串 u 和 v
$$ \begin{align} &u<_kv & \text{iff }u^k<v^k\\ &u=_kv & \text{iff }u^k=v^k\\ &u\le_kv & \text{iff }u^k\le v^k\\ \end{align} $$
性质

1. 对于k>=n ,$Suffix(i)<_kSuffix(j) $<=> $Suffix(i)<Suffix(j) $
2. $Suffix(i)=_{2k}Suffix(j) $<=> $Suffix(i)=_kSuffix(j) $ 且 $Suffix(i+k)=_kSuffix(j+k) $
3. $Suffix(i)<_{2k}Suffix(j) $<=> $Suffix(i)<_kSuffix(j) $ 或 ( $Suffix(i)=_kSuffix(j) $ 且$Suffix(i+k)<_kSuffix(j+k) $)

定义k- 后缀数组 $SA_k$

定义k- 名次数组 $Rank_k$

性质
$$ \begin{align} &Suffix(i)<_kSuffix(j) &\text{iff }Rank_k[i]<Rank_k[j]\\ &Suffix(i)=_kSuffix(j) &\text{iff }Rank_k[i]=Rank_k[j]\\ \end{align} $$

那么怎么构造k-数组呢

我们可以O(nlogn) 的用排序处理出 SA_1 与 Rank_1

然后O(n) 处理出 SA_2与 Rank_2

然后O(n) 处理出 SA_4与 Rank_4

总共log(n)次处理

所以可以在O(nlogn)的时间内处理出所有的k-后缀数组 SA 与 Rank