Algorithm to find the length of longest suffix between a String and a prefix of the String

Question

Input:

There is a long String S and we have a array of integers A which denotes the prefixes of the String S like A[i] denotes the prefix S[0..A[i]]

Output:

Return an array Output[] of the same size as A where Output[i] is the length of the longest matching suffix of S[0..A[i]] and S

Sample Input:

S = "ababa"
A[]=[0, 1, 2, 3, 4]

Sample Output:

Output[]=[1,0,3,0,5]

The most naive algorithm which I have is for every A[i] just match the number of characters between S[0..A[i]] and S from the end of both strings. But this algorithm is O(n^2) where n is the length of the original String S.

Question:
Is there is a better algorithm which pre processes the string S and then can quickly return the longest length suffix for the entire input Array?

Answer 1

This is just a Z-function of the reversed string. The slight difference is that the first element of the Z-function is chosen to be equal to the length of S. There is an algorithm to calculate the Z-function of a string in O(n)

And the algorithm for this problem is as follows:

• S' := reversed S
• Z := Z-function of S'
• for each i, Output[i] := Z[Len(S) - A[i] - 1]

For example:

S = "baabaaa"
A[] = [0,1,2,3,4,5,6]
Output[] should be [0,1,2,0,1,2,7]

S' = "aaabaab"
Z = Z-function(S') = [7,2,1,0,2,1,0] (with the first element chosen to be Len(S))