Finding presence of palindromic sequence in a string

Question

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 ?

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

score 1 · Answer 1 · answered Jul 25 '13 at 16:57

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.

score 0 · Answer 2 · edited May 23 '17 at 12:29

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?

edited May 23 '17 at 12:29

Community

1
1

answered Jul 25 '13 at 16:57

Eiyrioü von Kauyf

4,481
7
32
41

Finding presence of palindromic sequence in a string

2 Answers2