Online algorithm for checking palindrome in a stream | d is the number of characters in input alphabet ; q is a prime number used for evaluating Rabin Karp 's Rolling hash ; Length of input string ; A single character is always a palindrome ; Return if string has only one character ; Initialize first half reverse and second half for as firstr and second characters ; Now check for palindromes from second character onward ; If the hash values of ' firstr ' and ' second ' match , then only check individual characters ; Check if str [ 0. . i ] is palindrome using simple character by character match ; Calculate hash values for next iteration . Don 't calculate hash for next characters if  this is the last character of string ; If i is even ( next i is odd ) ; Add next character after first half at beginning of 'firstr   ; Add next character after second half at the end of second half . ; If next i is odd ( next i is even ) then we need not to change firstr , we need to remove first character of second and append a character to it . ; Driver program
d = 256 NEW_LINE q = 103 NEW_LINE def checkPalindromes ( string ) : NEW_LINE INDENT N = len ( string ) NEW_LINE print string [ 0 ] + " ▁ Yes " NEW_LINE if N == 1 : NEW_LINE INDENT return NEW_LINE DEDENT firstr = ord ( string [ 0 ] ) % q NEW_LINE second = ord ( string [ 1 ] ) % q NEW_LINE h = 1 NEW_LINE i = 0 NEW_LINE j = 0 NEW_LINE for i in xrange ( 1 , N ) : NEW_LINE INDENT if firstr == second : NEW_LINE INDENT for j in xrange ( 0 , i / 2 ) : NEW_LINE INDENT if string [ j ] != string [ i - j ] : NEW_LINE INDENT break NEW_LINE DEDENT DEDENT j += 1 NEW_LINE if j == i / 2 : NEW_LINE INDENT print string [ i ] + " ▁ Yes " NEW_LINE DEDENT else : NEW_LINE INDENT print string [ i ] + " ▁ No " NEW_LINE DEDENT DEDENT else : NEW_LINE INDENT print string [ i ] + " ▁ No " NEW_LINE DEDENT if i != N - 1 : NEW_LINE INDENT if i % 2 == 0 : NEW_LINE INDENT h = ( h * d ) % q NEW_LINE firstr = ( firstr + h * ord ( string [ i / 2 ] ) ) % q NEW_LINE second = ( second * d + ord ( string [ i + 1 ] ) ) % q NEW_LINE DEDENT else : NEW_LINE INDENT second = ( d * ( second + q - ord ( string [ ( i + 1 ) / 2 ] ) * h ) % q + ord ( string [ i + 1 ] ) ) % q NEW_LINE DEDENT DEDENT DEDENT DEDENT txt = " aabaacaabaa " NEW_LINE checkPalindromes ( txt ) NEW_LINE