Arj*_*jun 3 python string algorithm suffix-tree suffix-array
后缀数组将索引给定字符串列表的所有后缀,但如果您尝试索引所有可能的唯一子字符串,该怎么办？我对此有点新意,所以这是我的意思的一个例子:
鉴于字符串
abcd
后缀数组索引(至少根据我的理解)
(abcd,bcd,cd,d)
我想索引(所有子串)
(abcd,bcd,cd,d,abc,bc,c,ab,b,a)
我正在寻找一个后缀数组？如果是这样,我该怎么做才能将所有子字符串编入索引？如果没有,我应该在哪里看？还有什么我会谷歌对比"所有子串"与"后缀子串"？
jog*_*pan 15
后缀数组可以满足您的需要,因为每个子字符串都是其中一个后缀的前缀.具体来说,给出你的后缀数组
abcd bcd cd d
并假设您正在寻找子串"bc",那么您可以通过查找以"bc"开头的所有后缀(在这种情况下只有一个"bcd")来找到它.由于后缀数组按字典顺序排序,因此查找共享某个前缀的所有后缀对应于跨后缀数组的二进制搜索,结果将是后缀数组的一个连续范围的条目.
但是,使用后缀数组与辅助数据结构相结合的优化搜索方法,例如LCP(最长公共前缀)数组或小波树.有关此类方法的描述,请参阅纳瓦罗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个子字符串.