How do I find if a string contains a contiguous palindromic sequence ? I could try the naive solution in O(n^2) time where n is the string size , but any efficient algos to it ?
Asked
Active
Viewed 3,183 times
-2
-
possible duplicate of [Write a function that returns the longest palindrome in a given string](http://stackoverflow.com/questions/1115001/write-a-function-that-returns-the-longest-palindrome-in-a-given-string) – interjay Jul 25 '13 at 16:57
2 Answers
1
Well looking for just any palindrome isn't particularly interesting since every one character string is a palindrome. If you are looking for the longest palindrome you may be interested in Manacher's Algorithm.
A good description of the algorithm can be found here.
cyon
- 9,340
- 4
- 22
- 26
0
This is a quite common problem, and has ample results on google:
http://en.wikipedia.org/wiki/Longest_palindromic_substring
Rather than using Manacher's Algorithm you should use one of the parallel algorithms.
duplicate of : how to find longest palindromic subsequence?
Community
- 1
- 1
Eiyrioü von Kauyf
- 4,481
- 7
- 32
- 41