字符串操作 : calculate the "similarity of a string with its suffixes"

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

你要考虑suffix arrays .单词的后缀数组是按字典顺序排序的后缀索引数组。在链接的维基百科文章中，算法在计算后缀数组时计算 LCP(最长公共(public)前缀)。您可以使用与 suffix trees 的相似性在 O(n) 中进行计算，如图this paper .

示例:您的字符串是 ababaa，因此后缀数组如下所示:

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

其中左边的数字是后缀开始的索引。现在计算前缀非常容易，因为所有内容都是按字典顺序存储的。

作为旁注，这与 longest common substring 密切相关问题。要为下一次面试进行练习，请考虑有效解决问题的方法。