Online algorithm for checking palindrome in a stream

Given a stream of characters(charcaters are recieved one by one), write a function that will print 'yes' everytime, if the recieved characters till now forms a palindrome.

Example

INPUT
s = "bcdcb"

OUTPUT
YES  //'b' is a palindrome
NO   //'bc' is not a palindrome
NO   //'bcd' is not a palindrome
NO   //'bcdc' is not a palindrome
YES   //'bcdcb' is a palindrome

Method 1 (Simple Solution)

Algorithm

1. For every character in input string, check whether s[0..i] is a palindrome or not.

Method 2

In this method the main idea is to use the idea of Rolling hash used in Rabin Karp algorithm as the next hash value can be calculated from previous in O(1) time .
Keep track of reverse of first half and second half for every index

Algorithm

1. The first character is always a palindrome, so print yes for first character.

2. Initialize reverse of first half to the first character and second half to the second charcater. Let the hash value of first half reverse be 'FR' and that of second half be 'S'.

3. Traverse the string from second character
    a) If 'FR' and 'S' are same, then check iff s[0..i] is a palindrome using simple character by chracter match
    b) Update 'FR' and 'S' for next iteration.
        i) If 'i' is even, then add next character to the beginning of 'FR' and end of second half and update hash values.
        ii) If 'i' is odd, then keep 'FR' as it is, remove leading character from second and append a next character at end.

Working implementation of above algorithm

s = "bcdcb"
Initialize FR and S
FR = hash("b"), S = hash("c")
Traverse from second character
i = 1
    FR and S are not equal, so print NO
    update FR and S, i is odd so FR will not be changed and S becomes hash("d")
i = 2
    FR and S are not equal, so print NO
    update FR and S, i is even so FR becomes hash("cb") and S becomes hash("dc")
i = 3
    FR and S are not equal, so print NO
    update FR and S, i is odd so FR will not be changed and S becomes hash("cb")
i = 4
    FR and S are matched, so print YES
    No need to update, as it is the last index

C++ Program

#include <bits/stdc++.h>
using namespace std;
#define NO_OF_CHARS 256
// p is a prime number used for evaluating Rabin Karp's Rolling hash
#define p 103
 
void isPalindrome(char s[])
{
    // Length of input string
    int N = strlen(s);
 
    // first character is a palindrome
    cout<<s[0]<<" YES"<<endl;
 
    // Return if string has only one character
    if (N == 1) return;
 
    // Initialize first half reverse and S half for 
    // as FR and S characters
    int FR  = s[0] % p;
    int S = s[1] % p;
 
    int h = 1, i, j;
 
    // Now check for palindromes from S character
    // onward
    for (i=1; i<N; i++)
    {
        // If the hash values of 'FR' and 'S' 
        // match, then only check individual characters
        if (FR == S)
        {
            //check if s[0..i] is a palindorme
            for (j = 0; j < i/2; j++)
            {
                if (s[j] != s[i-j])
                    break;
            }
            if((j == i/2))
            {
                cout<<s[i]<<" YES"<<endl;
            }
            else
            {
                cout<<s[i]<<" NO"<<endl;
            }
        }
        else
        { 
            cout<<s[i]<<" NO"<<endl;
        }
 
        //update hash values
        if (i != N-1)
        {
            // If i is even (next i is odd) 
            if (i%2 == 0)
            {
                // Add next character after first half at beginning 
                // of 'FR'
                h = (h*NO_OF_CHARS) % p;
                FR  = (FR + h*s[i/2])%p;
                 
                // Add next character after S half at the end
                // of S half.
                S = (S*NO_OF_CHARS + s[i+1])%p;
            }
            else
            {
                // If i is odd (next i is even) then we
                // need not update FR, we need to remove
                // first character of S and append a
                // character to it.
                S = (NO_OF_CHARS*(S + p - s[(i+1)/2]*h)%p
                          + s[i+1])%p;
            }
        }
    }
}
 

int main()
{
    char s[] = "bcdcb";
    isPalindrome(s);
    return 0;
}
Try It

 


Next > < Prev
Scroll to Top