3 ms·

site is down? I hope this isn't just an O(N) algorithm using Suffix Arrays

• mjn 15y ago
  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.
  • shasta 15y ago
    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...
    • EricDeb 15y ago
      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
      • deleted 15y ago
        [deleted]
      • deleted 15y ago
        [deleted]
    • dhruvbird 15y ago
      substring is not subsequence in the context of this problem
• dhruvbird 15y ago
  Nope, see the section "A simple asymptotically optimal solution" - it doesn't use Suffix Arrays.