完整的后缀数组

Question

后缀数组将为给定的字符串列表索引所有后缀，但是如果您尝试对所有可能的唯一子字符串进行索引怎么办？我对此有些新意，因此这是我的意思的示例：

给定字符串

abcd

后缀数组索引（至少据我了解）

(abcd,bcd,cd,d)

我想索引（所有子字符串）

(abcd,bcd,cd,d,abc,bc,c,ab,b,a)

我想要的是后缀数组吗？如果是这样，我该怎么做才能索引所有子字符串？如果没有，我应该去哪里找？另外，我会用什么Google来对比“所有子字符串”与“后缀子字符串”？

Answer 1

后缀数组可以满足您的需要，因为每个子字符串都是后缀之一的前缀。具体来说，给定您的后缀数组

abcd bcd cd d

并假设您要查找子字符串“ bc”，那么可以通过查找所有以“ bc”开头的后缀（在这种情况下只有一个“
bcd”）来找到它。由于后缀数组是按字典顺序排序的，因此找到共享某个前缀的所有后缀都对应于后缀数组的二分查找，结果将是后缀数组的一个连续范围的条目。

但是，存在使用后缀数组和辅助数据结构（例如LCP（最长公共前缀）数组或小波树）组合的优化搜索方法。有关此类方法的说明，请参见Navarro的2007年调查（DOI
10.1145 / 1216370.1216372）。

考虑到下面的评论，我建议将每个后缀与其 表示 的 子字符串 数结合起来。在上面的简单示例中，这将是

4 abcd
3 bcd
2 bc
1 d

因为例如第一个后缀“ abcd”代表4个子字符串“ a”，“ ab”，“ abc”，“ abcd”。但是，在更复杂的示例中，假设对于字符串“
abcabxdabe”，后缀数组的前两个条目为

10 abcabxdabe
1 abe

因为第二个条目表示子字符串“ a”，“ ab”和“ abe”，但是“ a”和“ ab”也由第一个条目表示。

如何计算条目代表的子字符串数？->后缀的长度减去与前一个后缀共同的最长前缀的长度。例如，在“ abe”示例中，即3（其长度）减去2（“
ab”的长度，即与上一个条目共享的最长前缀）。因此，可以在后缀数组中一次生成这些数字，如果还生成了LCP（最长公共前缀）数组，则可以更快地生成这些数字。

下一步将是生成累计计数：

10 abcabxdabe
11 abe
16 abxdabe
...

然后找到一种有效的方法来利用累积的计数。例如，如果要按字典顺序获取第13个子字符串，则必须找到第一个条目，其累积计数大于或等于13。这就是上面的“ 16
abxdabe”。然后删除它与上一个条目共享的前缀（产生“ xdabe”），然后跳转到第二个字符之后的位置（因为上一个条目已累积了11，并且13-11 ==
2），因此您得到“ abxd”作为字典编排的第13个子字符串。