News for hackers. Stuff that matters.
Re:O(n) algorithm to find longest palindromic substring w/o ... by shasta on Sunday April 08, 2012 @09:43PM (#3815513)
S = "abcdefdcba" S' = "abcdfedcba"

So I suppose substring in this context is defined to be a subsequence of the string (not necessarily consecutive characters)? Site is down...

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

Re:O(n) algorithm to find longest palindromic substring w/o ... by dhruvbird on Sunday April 08, 2012 @10:31PM (#3815591)
substring is not subsequence in the context of this problem