对于两个字符串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。
ababaa
babaa
abaa
baa
aa
a
6,0,3,0,1,1
6 + 0 + 3 + 0 + 1 + 1 = 11
您要考虑后缀数组。单词的后缀数组是按字典顺序排序的后缀索引的数组。在链接的维基百科文章中，算法在计算后缀数组时会计算LCP（最长公共前缀）。如本文所示，您可以O(n)使用后缀树的相似性进行计算。
O(n)
示例：您的字符串为ababaa，因此后缀数组如下所示：
5 | a 4 | aa 2 | abaa 0 | ababaa 3 | baa 1 | babaa
其中左边的数字是后缀开始的索引。现在，由于前缀是按字典顺序存储的，每个人都可以计算前缀。
附带说明，这与最长的公共子字符串问题密切相关。要练习下一次面试，请考虑有效解决问题的方法。
