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;
}
