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?

Could you explain what `S[1..A[i]]` is supposed to be? The substring from `1` till `A[i]`? — Tim, Oct 07 '15 at 08:14
sorry updated the Question. it should have been `S[0..A[i]]` which is the substring from `0` till `A[i]` in S — pgiitu, Oct 07 '15 at 08:16
@Tim - the substring from position `0` to position `A[i]` in `S`. — shapiro yaacov, Oct 07 '15 at 08:16
If I understand the problem correctly the prefix should match the suffix, i.e. for `A[1]` the prefix would be `ab` and since the string doesn't end with `ab` `Output[1]` is 0. Is that correct? - With that assumption wouldn't it just suffice to see whether the string is symmetric? — Thomas, Oct 07 '15 at 08:21
@Thomas `A[1]` would actually be the substring `a`, so that's where I don't understand the example. — Tim, Oct 07 '15 at 08:22
@Tim we need to find the length of longest suffix between the Strings `S` and `S[0..A[i]]`. For Example `S="ababa"` and lets say `A[2]=2` so we need to find the length of the longest suffix between `"aba" (prefix S[0..2])` and `"ababa"` which would be `3` as `"aba"` is the longest suffix — pgiitu, Oct 07 '15 at 08:23
@Tim taking the comments into account I understand the prefix being the substring from 0 to `A[i]` i.e. from 0 to 1 (inclusive) in the example. At least the sample output makes sense that way. — Thomas, Oct 07 '15 at 08:24
@pgiitu can you add a more elaborate example to your question probably with a longer input string? As an example: if the input was `abaabaabaabaaba` and the prefix was `aba` would the longest suffix be `abaabaabaabaaba` with length 15 (or would it be length 5 since the suffix is 5 times the prefix) ? — Thomas, Oct 07 '15 at 08:26
@Thomas the longest suffix would be `aba`. Length of Suffix can be at max the length of short string between the two. — pgiitu, Oct 07 '15 at 08:28
Do you need Z-function? http://codeforces.com/blog/entry/3107 http://e-maxx-eng.github.io/string/z-function.html — MBo, Oct 07 '15 at 08:29
@MBo No I think Z function won't work for me. It is different from my problem. — pgiitu, Oct 07 '15 at 08:32
@pgiitu Why do you think Z is not work? I think it is the fastest solution. — Pham Trung, Oct 07 '15 at 08:33

Kolmar · Accepted Answer · 2015-10-07T12:53:51.353

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))

score -1 · Answer 2 · edited Oct 07 '15 at 09:13

The algorithm / datastructure you are looking for is called Suffix Tree it has a worst case complexity of O(n log n)

In computer science, a suffix tree (also called PAT tree or, in an earlier form, position tree) is a compressed trie containing all the suffixes of the given text as their keys and positions in the text as their values. Suffix trees allow particularly fast implementations of many important string operations. (wiki)

Here you can find some slides which explain the functionality and implemenation in detail

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

2 Answers2