Find the longest prefix of a string s that is a substring of the reversal of the string s

Question

Are there any ways to use linear-time algorithm to find the longest prefix of a string s that is a substring of the reversal of the string s?

Answer 1

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

Answer 2

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

1. Computing srev, the reversal of string s, is O(n) (and actually it can be O(1), but it doesn't matter here).
2. A suffix tree for srev can be built in O(n) time.
3. Longest prefix of s in srev can be found in O(n) time using the suffix tree.