字符串操作:计算"字符串与其后缀的相似性"

Question

对于两个字符串A和B,我们将字符串的相似性定义为两个字符串共有的最长前缀的长度.例如,字符串"abc"和"abd"的相似性是2,而字符串"aaa"和"aaab"的相似性是3.

问题是给出一个算法来计算字符串S与每个后缀的相似之和.例如,让字符串为:ababaa.然后,该字符串的后缀ababaa,babaa,abaa,baa,aa和a.每个这些字符串与所述串的的相似之处ababaa是6,0,3,0,1,1,分别.答案是这样的6 + 0 + 3 + 0 + 1 + 1 = 11.

Answer 1

您想要考虑后缀数组.单词的后缀数组是按字典顺序排序的后缀索引的数组.在链接的维基百科文章中,算法在计算后缀数组时计算LCP(最长公共前缀).您可以O(n)使用后缀树的相似性来计算此值,如本文所示.

示例:您的字符串是ababaa,所以后缀数组如下所示:

5 | a
4 | aa
2 | abaa
0 | ababaa
3 | baa
1 | babaa

左边的数字是后缀开始的索引.现在每个计算前缀都非常好,因为所有内容都是按字典顺序存储的.

作为旁注,这与最长的常见子串问题密切相关.要练习下一次面试,请考虑有效解决问题的方法.