News for hackers. Stuff that matters.
Re:O(n) algorithm to find longest palindromic substring w/o ... by mjn on Sunday April 08, 2012 @08:33PM (#3815365)
From Google Cache, this one exploits the theorem (which the page proves) that the longest palindromic substring of a string S is the longest common substring between S and its reversal S'. Since there are linear-time longest-common-substring algorithms, finding longest palindromes therefore is linear time. It doesn't actually say which LCS algorithm they'd use, since the page is more about the proof. They even admit that it probably isn't the best approach in practice.
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