15,997,776 members
See more:
Hi
can you tell me the best way to find longest palindrome sub string in a string.
please explain .i got lot of link but not able to understand
Posted
Updated 21-Apr-23 0:28am
[no name] 14-Apr-13 8:58am
How could we possibly know what it is that you do not understand?
ravi1989h 14-Apr-13 9:01am
actually can please explain steps..they are using tree. first they reverse the string .then find prefix or sufix.that thing i am not able to understand please explain with example.
Can you show the code you have found and which you can't follow
There are lots of sources out there, as you have said.
Do you mean you don't understand the code they use?
Or that you don't fully understand the language used (presuming English isn't your first language)?

The obvious approach of taking each letter of the string and working away from it in both directions appears to be the least efficient (but it should be simple to code). Do you need to find 'better' answers?

## Solution 1

There is a good talk through of this problem, complete with a pretty much optimal algorithm here:
http://www.akalin.cx/longest-palindrome-linear-time[^]
It works by looking for palindromes from the centers, which is such a bright idea that it makes you go ":doh:! Why didn't I think of that?".

I leave it as an exercise for the reader to implement it in C - but it doesn't need any trees at all!

JayantaChatterjee 14-Apr-13 10:21am
My 5 for the Algorithm....
OriginalGriff 14-Apr-13 10:29am
I'm impressed with it - it's one of those you should have thought of to start with really, but I am clearly not bright enough to do it! :laugh:
ravi1989h 14-Apr-13 12:13pm
from here i found
http://stackoverflow.com/questions/7043778/longest-palindrome-in-a-string-using-suffix-tree
ravi1989h 14-Apr-13 12:13pm
check this

http://stackoverflow.com/questions/7043778/longest-palindrome-in-a-string-using-suffix-tree
ravi1989h 14-Apr-13 12:20pm
http://tristan-interview.blogspot.in/2011/11/longest-palindrome-substring-manachers.html

please explain with example not able to understand

## Solution 4

If this is a assignment than I believe you need to know about Manacher's Algorithm to solve your problem.

Otherwise if you are just doing it for fun , for simplicity purposes you can use the below steps to achieve what you want as well :
Step 1 : Find all the palindromes in the string .
Step 2 : Count the characters of each of the palindrome strings that you have found.
Step 3 : Congrats , You have found the largest palindrome text .

Richard Deeming 21-Apr-23 6:32am
As already covered in solution 1, which was posted ten years ago.
Prilvesh K 21-Apr-23 7:02am
It's good for the readers to know the name of the Algorithm being used .
As the solution & nor the link https://www.akalin.com/longest-palindrome-linear-time mention that " Manacher's Algorithm" is the name of the algorithm being used.

Multiple urls being posted in the comments section is ambiguous so giving a tertiary level direction on the expected algorithm with its proper name is helpful .
Richard Deeming 21-Apr-23 7:14am
So post that as a comment on solution 1.

Naming the algorithm used in the previous solution doesn't warrant a whole new solution. And there's nothing in your solution to suggest the "Manacher's Algorithm" is the one mentioned in solution 1.
Prilvesh K 21-Apr-23 7:21am
The point of my solution is 2 fold .
1) Redirect anyone confused to know about Manacher's Algorithm
2) Provide alternate solution way to solve the same problem as indicated by steps 1-3
Thus the new solution,
It all comes down to providing clarity to the would be readers that need help, In this case now its crystal clear that Manacher's Algorithm is the way to go ! .