3

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

给定字符串

abcd

后缀数组索引（至少在我的理解中）

(abcd,bcd,cd,d)

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

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

我正在寻找后缀数组吗？如果是这样，我该怎么做才能索引所有子字符串？如果没有，我应该在哪里寻找？另外我会用谷歌来对比“所有子字符串”与“后缀子字符串”吗？

4

3 回答 3

15

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

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”），然后跳转到第2个字符之后的位置（因为前一个条目已经累积计数11，并且13-11==2），所以你得到“ abxd" 按字典顺序排列为第 13 个子字符串。

于 2012-02-22T07:04:22.917 回答
1

正如已经回答的那样，子字符串是后缀的前缀。有时您可能想换一种方式获得前缀的后缀。

除此之外，还不清楚您要使用“唯一子字符串”寻找什么。我建议你查一下这些词：类型、令牌、最大值、超最大值。在后缀数组文献中找到这些应该没有问题。

于 2012-02-22T16:47:13.420 回答
0

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

于 2012-02-22T06:45:47.810 回答