Re:O(n) algorithm to find longest palindromic substring w/o ...
by EricDeb on Sunday April 08, 2012 @10:07PM
(#3815559)
Ooh if it's a subsequence I am not aware of the solution. For a substring though, you can just concatenate S and its reverse , find the suffix array and corresponding height array in O(n), and parse through the suffix array looking for suffixes with high height array values where one suffix is from S and the next suffix is from its reverse.
Generally speaking anything you can do with a suffix tree you can do with suffix arrays... though oftentimes it is more complicated
Generally speaking anything you can do with a suffix tree you can do with suffix arrays... though oftentimes it is more complicated