完整后缀数组

Question

后缀数组将索引给定字符串列表的所有后缀，但是如果您试图索引所有可能的唯一子字符串，该怎么办？我对这个有点陌生，所以这里有一个我的意思的例子：

给我一根绳子

abcd

后缀数组索引（至少在我看来）

^{pr2}$

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

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

我要找的是后缀数组吗？如果是的话，我该怎么做才能使所有的子字符串都索引起来？如果没有，我应该在哪里找呢？还有，我可以用谷歌来对比“所有子字符串”和“后缀子字符串”吗？在

Answer 1

你应该使用“Trie”的变体。本质上，如果您有ABCD，创建树，它是路径的合并：根->；a->；B->；C->；D、root->；B->；C->；D、root->；C->；D和root->；D。现在，在每个节点都保留一个观察到字符串root->；->；节点的位置列表。在

Answer 2

后缀数组可以满足您的需要，因为每个子字符串都是其中一个后缀的前缀。特别是，给定后缀数组

abcd bcd公司 光盘 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”、“abc”。但是，在一个更复杂的示例中，比如对于字符串“abcabxdabe”，后缀数组的前两个条目将是

^{pr2}$

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

如何计算一个条目所代表的子串数？>；后缀的长度减去它与前一个后缀相同的最长前缀的长度。E、 g.在“abe”示例中，即3（它的长度）减去2（“ab”的长度，它与前一个条目共享的最长前缀）。因此，这些数字可以通过后缀数组一次生成，如果还生成了LCP（最长公共前缀）数组，则速度更快。在

下一步是生成累计计数：

10 abcabxdabe
11 abe
16 abxdabe
...

然后找到一种有效的方法来利用累积计数。E、 如果你想用字典法得到第13个子串，你必须找到第一个累计计数大于或等于13的条目。那就是上面的“16 abxdabe”。然后删除它与前一个条目共享的前缀（产生“xdabe”），然后跳转到第二个字符之后的位置（因为前一个条目累积了count 11，并且13-11==2），这样您就得到了“abxd”作为第13个子串。在

Answer 3

正如已经回答过的，子串是后缀的前缀。有时你可能会想换一种方式，得到前缀的后缀。在

除此之外，你还不清楚你要用“独特的子串”来寻找什么，我建议你查一下这些词：type，token，maximal，supermax。在后缀数组文献中找到它们应该没有问题。在