Online algorithm for checking palindrome in a stream | Java program for online algorithm for palindrome checking ; 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 to test above function
public class GFG { static final int d = 256 ; static final int q = 103 ; static void checkPalindromes ( String str ) { int N = str . length ( ) ; System . out . println ( str . charAt ( 0 ) + " ▁ Yes " ) ; if ( N == 1 ) return ; int firstr = str . charAt ( 0 ) % q ; int second = str . charAt ( 1 ) % q ; int h = 1 , i , j ; for ( i = 1 ; i < N ; i ++ ) { if ( firstr == second ) { for ( j = 0 ; j < i / 2 ; j ++ ) { if ( str . charAt ( j ) != str . charAt ( i - j ) ) break ; } System . out . println ( ( j == i / 2 ) ? str . charAt ( i ) + " ▁ Yes " : str . charAt ( i ) + " ▁ No " ) ; } else System . out . println ( str . charAt ( i ) + " ▁ No " ) ; if ( i != N - 1 ) { if ( i % 2 == 0 ) { h = ( h * d ) % q ; firstr = ( firstr + h * str . charAt ( i / 2 ) ) % q ; second = ( second * d + str . charAt ( i + 1 ) ) % q ; } else { second = ( d * ( second + q - str . charAt ( ( i + 1 ) / 2 ) * h ) % q + str . charAt ( i + 1 ) ) % q ; } } } } public static void main ( String args [ ] ) { String txt = " aabaacaabaa " ; checkPalindromes ( txt ) ; } }