Online algorithm for checking palindrome in a stream | C 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
#include <stdio.h> NEW_LINE #include <string.h> NEW_LINE #define d  256 NEW_LINE #define q  103 NEW_LINE void checkPalindromes ( char str [ ] ) { int N = strlen ( str ) ; printf ( " % c ▁ Yes STRNEWLINE " , str [ 0 ] ) ; if ( N == 1 ) return ; int firstr = str [ 0 ] % q ; int second = str [ 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 [ j ] != str [ i - j ] ) break ; } ( j == i / 2 ) ? printf ( " % c ▁ Yes STRNEWLINE " , str [ i ] ) : printf ( " % c ▁ No STRNEWLINE " , str [ i ] ) ; } else printf ( " % c ▁ No STRNEWLINE " , str [ i ] ) ; if ( i != N - 1 ) { if ( i % 2 == 0 ) { h = ( h * d ) % q ; firstr = ( firstr + h * str [ i / 2 ] ) % q ; second = ( second * d + str [ i + 1 ] ) % q ; } else { second = ( d * ( second + q - str [ ( i + 1 ) / 2 ] * h ) % q + str [ i + 1 ] ) % q ; } } } } int main ( ) { char * txt = " aabaacaabaa " ; checkPalindromes ( txt ) ; getchar ( ) ; return 0 ; }