How to detect the first occurrence of palindrome

Question

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

Answer 1

One approximate solution that should be running in linear time O(n) in most cases is to use rolling hash.

You keep track of the hash of the string and its reverse. Every time you read a new character, you could update the two hash values in O(1). Then you compare the two hashes, if they are equal, then you compare the string and its reserve. If this is also equal, exits and you got a palindrome.

For example one very simple rolling hash function is hash(ck c(k-1).. c0) = (p^k*ck + p^(k - 1) * c(k - 1) + ... + c0) mod m where p is an odd prime.

So start with:

p = 17 // or your lucky prime number
m = 10^9 // ...
hash = 0
hash_rev = 0
str = ''
str_rev = ''
p_pow = 1    

while True
    read c
    append c to str
    prepend c to str_rev
    hash = (hash * p + c) mod m
    hash_rev = (hash_rev + p_pow * c) mod m
    p_pow = p_pow * p
    if hash == hash_rev
         if str == str_rev
             found str to be the first palindrome

To make it even faster, you can decleare your hash and hash_rev to be 32 bit integer and pick m = 2^32. Then you can ignore the (mod m) operation.

Answer 2

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