Find the longest prefix of string s, which is a substring of string s

Question

Is there a way to use a linear time algorithm to find the longest prefix of string s, which is a substring of string s?

Answer 1

Apply the Knuth-Morris-Pratt algorithm to search for a given string (S) in reverse order (T). At each iteration, he will find the longest prefix S, which is the suffix T [1..i]. Then you just need to find the maximum lengths of these prefixes.

Answer 2

Yes, there is a solution O(n)with a suffix tree. Suppose that nis the length of a string s.

• Calculation s rev, s, O(n) ( O(1), ).
• s rev O(n) .
• s s rev O(n) , .