How to detect the first occurrence of palindrome

Asked 2012-04-09T05:20:39.757

Suppose you are reading from a character stream, the function should return when you have read the first occurrence of palindrome.

The length of the palindrome should be even number.

The requirement of the time complexity is O(N).

Example:

1st character: 4
2nd character: 1
3rd character: 3
4th character: 3
5th character: 1
6th character: 4, return

algorithm palindrome

Edit Report

2 Answers

Return when you read the first character, that's a one-letter palindrome.

answered 2012-04-09T05:24:49.923

What you need is a slight modification of Manacher's Algorithm. It allows you to find all palindromes in a string in linear time. The thing about algorithm it, that it actually proceeds from left, to right, "using" new chars when needed. The modification needed, is that you need to read new character, only when you try to access it.
Stop, if you found palindrome, that goes all way back to the beginning of the stream.

answered 2012-04-09T06:14:46.820

How to detect the first occurrence of palindrome

2 Answers

Your Answer