News for hackers. Stuff that matters.
Re:O(n) algorithm to find longest palindromic substring w/o ... by VDegesys on Sunday April 08, 2012 @11:48PM (#3815756)
I'm honestly just curious and I could be missing something trivial... but how does the "simple asymptotically optimal solution" take into account an even length palindrome? in the sense of "deed" where there are never matching letters to the left and right of the interesting position...i think it would still be O(n) but I just don't see the algorithm taking it into account...
Re:O(n) algorithm to find longest palindromic substring w/o ... by bbi5291 on Monday April 09, 2012 @12:59AM (#3815891)
Quoting the article: "Every palindromic substring has a centre. For an odd-length substring, this is its middle character; for an even-length substring, this is the imaginary space between its two middle characters. Call each character and each space in the original string a position. Then there are 2N+1 positions in any string of length N (to simplify things later on, we assume there is a position just before the first character and one just after the last), and any longest palindromic substring must have one of these as its centre."
Re:O(n) algorithm to find longest palindromic substring w/o ... by VDegesys on Monday April 09, 2012 @02:07AM (#3815991)
ah perfect. thanks... skimmed right over it... apparently easter wore me out...