Longest palindrome in a string

Question

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 14-Apr-13 2:40am

ravi1989h

Updated 21-Apr-23 0:28am

Add a Solution

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?

2 solutions

Add a Solution

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

OriginalGriff · Answer 1 · 2013-04-14T03:24:00

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!

Posted 14-Apr-13 3:24am

OriginalGriff

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

Prilvesh K · Answer 2 · 2023-04-21T00:28:00

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 .

Posted 21-Apr-23 0:28am

Prilvesh K

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 ! .

Longest palindrome in a string

2 solutions

Solution 1

Solution 4

Add your solution here

Preview 0

Longest palindrome in a string

2 solutions

Solution 1

Solution 4

Add your solution here

Preview 0

Existing Members

...or Join us