Online algorithm for checking palindrome in a stream - GeeksforGeeks
Given a stream of characters (characters are received one by one), write a function that prints 'Yes' if a character makes the complete string palindrome, else prints 'No'.
Rolling Hash used in Rabin Karp algorithm. The idea is to keep track of reverse of first half and second half (we also use first half and reverse of second half) for every index.
http://blueocean-penn.blogspot.com/2015/05/rabin-karp-algorithm.html
http://allenlipeng47.com/PersonalPage/index/view/157/nkey
Read full article from Online algorithm for checking palindrome in a stream - GeeksforGeeks
Given a stream of characters (characters are received one by one), write a function that prints 'Yes' if a character makes the complete string palindrome, else prints 'No'.
Input: str[] = "abcba"
Output: a Yes // "a" is palindrome
b No // "ab" is not palindrome
c No // "abc" is palindrome
b No // "abcb" is not palindrome
a Yes // "abcba" is palindrome
Rolling Hash used in Rabin Karp algorithm. The idea is to keep track of reverse of first half and second half (we also use first half and reverse of second half) for every index.
1) The first character is always a palindrome, so print yes for
first character.
2) Initialize reverse of first half as "a" and second half as "b".
Let the hash value of first half reverse be 'firstr' and that of
second half be 'second'.
3) Iterate through string starting from second character, do following
for every character str[i], i.e., i varies from 1 to n-1.
a) If 'firstr' and 'second' are same, then character by character
check the substring ending with current character and print
"Yes" if palindrome.
Note that if hash values match, then strings need not be same.
For example, hash values of "ab" and "ba" are same, but strings
are different. That is why we check complete string after hash.
b) Update 'firstr' and 'second' for next iteration.
If 'i' is even, then add next character to the beginning of
'firstr' and end of second half and update
hash values.
If 'i' is odd, then keep 'firstr' as it is, remove leading
character from second and append a next
character at end.
// d is the number of characters in input alphabet#define d 256// q is a prime number used for evaluating Rabin Karp's Rolling hash#define q 103void checkPalindromes(char str[]){ // Length of input string int N = strlen(str); // A single character is always a palindrome printf("%c Yes\n", str[0]); // Return if string has only one character if (N == 1) return; // Initialize first half reverse and second half for // as firstr and second characters int firstr = str[0] % q; int second = str[1] % q; int h = 1, i, j; // Now check for palindromes from second character // onward for (i=1; i<N; i++) { // If the hash values of 'firstr' and 'second' // match, then only check individual characters if (firstr == second) { /* Check if str[0..i] is palindrome using simple character by character match */ for (j = 0; j < i/2; j++) { if (str[j] != str[i-j]) break; } (j == i/2)? printf("%c Yes\n", str[i]): printf("%c No\n", str[i]); } else printf("%c No\n", str[i]); // Calculate hash values for next iteration. // Don't calculate hash for next characters if // this is the last character of string 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 'firstr' h = (h*d) % q; firstr = (firstr + h*str[i/2])%q; // Add next character after second half at the end // of second half. second = (second*d + str[i+1])%q; } else { // 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. second = (d*(second + q - str[(i+1)/2]*h)%q + str[i+1])%q; } } }}http://blueocean-penn.blogspot.com/2015/05/rabin-karp-algorithm.html
| public class RabinKarpString { static final int prime = 101; | |
| static final int base = 103; | |
| public static void rabinKarp(String s){ | |
| assert(s!=null && !s.isEmpty()); | |
| long leftHash = s.charAt(0); | |
| long rightHash = s.charAt(0); | |
| System.out.println("Yes"); | |
| int h = 1; | |
| for(int i = 1; i < s.length(); i++){ | |
| h = (h*prime)%base; | |
| leftHash = (leftHash*prime + s.charAt(i))%base; | |
| rightHash = ( (long) (s.charAt(i)*h + rightHash))%base; | |
| if(leftHash == rightHash){ | |
| isPali(s, i); | |
| }else | |
| System.out.println("No"); | |
| } | |
| } | |
| public static void isPali(String s, int i){ | |
| for(int l=0,r=i; l<=r; l++, r--){ | |
| if(s.charAt(l) != s.charAt(r)){ | |
| System.out.println("No"); | |
| } | |
| } | |
| System.out.println("Yes"); | |
| } | |
| } |
Read full article from Online algorithm for checking palindrome in a stream - GeeksforGeeks
