String manipulation: calculate the "similarity of a string with its suffixes"

Question

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.

Answer 1

You want to consider suffix arrays. The suffix array of a word is the array of the indices of suffixes sorted in lexicographical order. In the linked wikipedia article, the algorithms compute the LCP (longest common prefix) as they compute the suffix array. You can compute this in O(n) using similarities with suffix trees, as shown in this paper.

EXAMPLE: Your string is ababaa, so the suffix array looks like this:

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

where the number on the left is the index at which the suffix begins. Now it's pretty each to compute prefixes since everything is stored lexicographically.

As a side note, this is closely related to the longest common substring problem. To practice for your next interview, think about ways to solve that efficiently.

Answer 2

Read this link about z-algorithm first. An O(n) solution based on the algorithm from the link implemented on python:

def z_func(s):
    z = [0]*len(s)
    l, r = 0, 0
    for i in range(1,len(s)):
        if i<=r:
            z[i] = min(r-i+1, z[i-l])
        while (i + z[i] < len(s) and s[z[i]] == s[i + z[i]]):
            z[i] += 1
        if z[i]+i-1 > r:
            l, r = i, z[i]+i-1
    return sum(z)+len(s)