Q:

How to detect the first occurrence of palindrome

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

A:

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

A:

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.

A:

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.

