对于两个字符串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.