Longest Palindrome in String

[shwetank_gupta]

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

[Ledidas]

You problem is supposed to be another form of longest common substring, which the suffix tree seems best fitted in terms of time complexity, with only trade-off for space and extra steps in tree building. The current O(n^2) looks founded and widely used until some striking alternative approach hits the journal in the very near future, I hope.

[ShadeOfBlue]

Hi, I found this link
http://portal.acm.org/citation.cfm?id=1840177
it is computeing longest palindrome in linear time and space.

But it asks me to pay. Anyone knows its content, pseudoalgorithm to do that ?

[BioPhysEngr]

Perhaps this link may be of use: http://www.akalin.cx/2007/11/28/find...n-linear-time/

[ShadeOfBlue]

They provided translated code that works incorrectly,
For this string
dcfcdhihijkjihjfccccccccccabcdefggfedcba
the last C++ source code returns cccccccccc, I think this is the purpose of the program, as the second loop only counts indices in case of equal characters encountered to retrieve its length, there is no check for palindromes. that is why it takes O(n). (Just my brief reading)

[Khiem]

Well the last source code is written in C#,

[BioPhysEngr]

Oh, sorry; I wasn't reading carefully. I read your main post a few days ago and neglected to see that you included the same link I gave you. >__<