I am looking for O(N) solution to the problem of finding longest palindrome in a string
in linear time-complexity...
I got a link in which this problem is described....but i m not able to understood it clearly
(how it reduces from O(N^2) to O(N) complexity...)
Link: http://www.akalin.cx/2007/11/28/find...n-linear-time/
I am very confused with "what is the palindromic proper suffix and how we find it out"
also how "given a current center, the longest palindrome around that center, and a list of the lengths of the longest palindromes around the centers to the left of the current center, can we figure out the new center to consider and extend the list of longest palindrome lengths up to that center efficiently?"
Please, reply.
PS: Please ignore the suffix tree approach