For two strings A and B, we define the similarity of the strings to be the length of the longest prefix common to both strings. For example, the similarity of strings "abc" and "abd" is 2, while the similarity of strings "aaa" and "aaab" is 3.
The problem is to give an algorithm to calculate the sum of similarities of a string S with each of it's suffixes. For example, let the string be : ababaa
. Then, the suffixes of the string are ababaa
, babaa
, abaa
, baa
, aa
and a
. The similarities of each of these strings with the string ababaa
are 6,0,3,0,1,1
, respectively. Thus the answer is 6 + 0 + 3 + 0 + 1 + 1 = 11
.