CODEWITHSUNDEEP
javaalgorithm
user605947
user605947

Reputation: 119

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

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?

Upvotes: 4

Views: 2078

Answers (2)

rlibby
rlibby

Reputation: 6021

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.

Upvotes: 4

adamax
adamax

Reputation: 3865

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.

Upvotes: 4

Related Questions