后缀数组将索引给定字符串列表的所有后缀，但是如果您要索引所有可能的唯一子字符串，该怎么办？我在这个有点新的，所以这里是我的意思的例子：完整的后缀数组
鉴于串
abcd
后缀数组索引（至少我的理解）
(abcd,bcd,cd,d)
我想索引（所有的子串）
(abcd,bcd,cd,d,abc,bc,c,ab,b,a)
是我想找的后缀数组吗？如果是这样，我该如何获取所有的子字符串索引？如果不是，我应该在哪里看？还有什么我谷歌对比“所有子字符串”与“后缀子字符串”？
后缀数组完成你所需要的，因为每个子字符串都是其中一个后缀的前缀。具体地，给出你的后缀数组
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级的子串“一”，“AB”，“ABC”，“ABCD”。然而，在更复杂的例子，说字符串“abcabxdabe”，后缀数组的前两个条目是
10 abcabxdabe
1 abe
因为第二项表示子串“一”，“AB”和“安倍” ，但是“a”和“ab”也由第一项表示。
如何计算一个条目表示的子字符串的数量？ - >后缀的长度减去它与前一个后缀共有的最长前缀的长度。例如。在“abe”示例中，即3（其长度）减2（“ab”的长度，它与前一个条目共享的最长前缀）。因此，这些数字可以通过后缀数组一次生成，如果还生成了LCP（最长公共前缀）数组，则速度更快。
下一步将产生累积计数：
10 abcabxdabe
11 abe
16 abxdabe
...
，然后找到一种有效的方式来利用累积计数。例如。如果你想按字典顺序得到第13个子字符串，你必须找到第一个累计数大于或等于13的条目。这将是上面的“16 abxdabe”。然后删除与前一个条目共享的前缀（产生“xdabe”），然后跳转到第二个字符后面的位置（因为前一个条目已经累计了11和13-11 == 2），所以你得到“ abxd“作为第13个子字符串。
不错，我想到了这一点，但是如果我想按照字典顺序查找第n个子字符串，该怎么办。我不需要遍历数组并为非后缀子字符串添加条目吗？因为如果我检索索引为n的子字符串，这只会计算后缀。我有什么意义吗？对不起，如果我不.. – Arjun 2012-02-22 07:12:10
我明白了，是的，这是有道理的。我误解了你最初的“索引”的含义。但我相信你所要求的也可以使用稍微扩大的后缀数组来完成。具体而言，可以将数组中的每个后缀与一个数字组合起来，以指示它代表了多少个唯一的子字符串。它所表示的_substrings基本上是它所包含的前缀，减去前面后缀所代表的前缀。我将通过编辑答案来描述这些细节。 – jogojapan 2012-02-22 07:32:42
谢谢你的优雅的解决方案。我目前正在生成LCP数组，所以这看起来应该可以工作。非常感谢您的帮助，如果结果正常，我会通知您！ – Arjun 2012-02-24 06:45:38
您应该使用'Trie'的变体。实质上，如果你有ABCD，创建一个合并路径的树：root-> A-> B-> C-> D，root-> B-> C-> D，root-> C-> D和root - > d。现在，在每个节点都保留一个位置列表，其中字符串root - > .-> .->节点被观察到。
谢谢，我会检查出这种替代方法为好。 – Arjun 2012-02-24 06:56:30
正如已经回答的那样，子字符串是后缀的前缀。有时候你可能会想换一种方式来获取前缀的后缀。
除此之外，目前还不清楚你在寻找什么“独特的子串”。我建议你查看单词：类型，标记，最大值，超大值。在后缀数组文献中找到这些应该没有问题。
对我来说，有一种稍微有趣的方式来说相同的事情。一旦你得到你的后缀数组并运行，收集一系列关于后缀数组的文件并通过你的程序运行它们。你会看到在该领域使用了哪些技术词汇。如果你睁大眼睛，你可能会得到一些惊喜。当然，如果你自己写一篇论文，那么通过后缀数组运行。不要忘记具有特殊属性的数字类型的字符串。请享用！用后缀数组更好地生活！ – 2012-02-22 20:26:11
您的SA语料库必须包含Abouelhoda et al。我会添加Kim等人的“线性后缀树”论文。后者有一个很好的“文学评论”部分，这真的有助于通过Abouelhoda一些比较晦涩的部分。对于来自“休闲数学”视角的后缀数组，请阅读KlausSchürman的书。 – 2012-02-22 21:20:35
您的SA语料库必须包含Abouelhoda et al。我会添加Kim等人的“线性后缀树”论文。后者有一个很好的“文学评论”部分，这真的有助于通过Abouelhoda一些比较晦涩的部分。对于来自“休闲数学”视角的后缀数组，请阅读KlausSchürman的书。 （特别提示）查看加斯菲尔德在加州大学戴维斯分校的录像带讲座。 – 2012-02-22 21:40:34
看到这个： http://stackoverflow.com/questions/2560262/generate-all-unique-substrings-for-given-string – 2012-02-22 06:05:29