Click here to Skip to main content
15,905,232 members
Please Sign up or sign in to vote.
1.00/5 (3 votes)
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
Comments
[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.
M-Badger 14-Apr-13 9:15am    
Can you show the code you have found and which you can't follow
M-Badger 14-Apr-13 9:11am    
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?

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!
 
Share this answer
 
Comments
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
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 .
 
Share this answer
 
Comments
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 ! .

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900