4、后缀数组 Suffix Array
后缀数组是后缀树的一种节省空间的替代方法,后缀树本身是trie的压缩版本。
后缀数组可以完成后缀树可以完成的所有工作,并且带有一些其他信息,例如最长公共前缀(LCP)数组
4.1、后缀数组格式
如下图,字符串:arthinking,所有的后缀,从长到短列出来:
给后缀排序,排序后对应的索引构成的数组既是后缀数组:
后缀数组sa:后缀suffix列表排序后,suffix的下标构成的数组sa;
rank:suffix列表每个元素的排位权重(权重越大排越后面);
4.2、后缀数组构造过程
上面的后缀构造过程是怎样的呢?
这里我们介绍最常见的倍增算法
来得到后缀数组。
我们获取每一个元素的权重rank,获取到之后,依次继续
- 第0轮:suffix[i] = suffix[i] + suffix[2^0],重新评估rank;
- 第1轮:suffix[i] = suffix[i] + suffix[2^1],重新评估rank;
- …
- 第n轮:suffix[i] = suffix[i] + suffix[2^n],重新评估rank;
- …
最终得到所有rank都不相等即可。如下图所示:
这样就得到rank了,我们可以根据rank很快推算出sa数组。
为什么可以这样倍增,跳过中间某些元素进行比较呢?
这是一种很巧妙的用法,因为每个后缀都与另一个后缀有一些共同之处,并不是随机字符串,迁移轮比较,为后续比较垫底了基础。
假设要处理
substr(i, len)
子字符串。我们可以把第k轮substr(i, 2^k)
看成是一个由substr(i, 2^k−1)
和substr(i + 2^k−1, 2^k−1)
拼起来的东西,而substr(i, 2^k−1)
的字符串是上一轮比较过的并且得出了rank。
4.3、后缀数组使用场景
- 在较大的文本中查找子字符串的所有出现;
- 最长重复子串;
- 快速搜索确定子字符串是否出现在一段文本中;
- 多个字符串中最长的公共子字符串
- …
LCP数组
最长公共前缀(LCP longest common prefix)数组,是排好序的suffix数组,用来跟踪获取最长公共前缀(LCP longest common prefix)。