## Saturday, July 9, 2016

### Palindrome Substring Queries - GeeksforGeeks

Palindrome Substring Queries - GeeksforGeeks
Given a string and several queries on the substrings of the given input string to check whether the substring is a palindrome or not.

The idea is similar to Rabin Karp string matching. We use string hashing. What we do is that we calculate cumulative hash values of the string in the original string as well as the reversed string in two arrays- prefix[] and suffix[].
How to calculate the cumulative hash values ?
Suppose our string is str[], then the cumulative hash function to fill our prefix[] array used is-
```prefix[0] = 0
prefix[i] = str[0] + str[1] * 101 + str[2] * 1012 +
...... + str[i-1] * 101i-1

For example, take the string- “abaaabxyaba”

prefix[0] = 0
prefix[1] = 97  (ASCII Value of ‘a’ is 97)
prefix[2] = 97 + 98 * 101
prefix[3] = 97 + 98 * 101 + 97 * 1012
...........................
...........................
prefix[11] = 97 + 98 * 101 + 97 * 1012 +
........+ 97 * 10110 ```
Now the reason to store in that way is that we can easily find the hash value of any substring in O(1) time using-
``` hash(L, R) = prefix[R+1] – prefix[L]
```
For example, hash (1, 5) = hash (“baaab”) = prefix[6] – prefix[1] = 98 * 101 + 97 * 1012 + 97 * 1013 + 97 * 1014 + 98 * 1015 = 1040184646587 [We will use this weird value later to explain what’s happening].
`// Structure to represent a query. A query consists`
`// of (L,R) and we have to answer whether the substring`
`// from index-L to R is a palindrome or not`
`struct` `Query`
`{`
`    ``int` `L, R;`
`};`

`// A function to check if a string str is palindrome`
`// in the ranfe L to R`
`bool` `isPalindrome(string str, ``int` `L, ``int` `R)`
`{`
`    ``// Keep comparing characters while they are same`
`    ``while` `(R > L)`
`        ``if` `(str[L++] != str[R--])`
`            ``return``(``false``);`
`    ``return``(``true``);`
`}`

`// A Function to find pow (base, exponent) % MOD`
`// in log (exponent) time`
`unsigned ``long` `long` `int` `modPow(unsigned ``long` `long` `int` `base,`
`                              ``unsigned ``long` `long` `int` `exponent)`
`{`
`    ``if` `(exponent == 0)`
`        ``return` `1;`
`    ``if` `(exponent == 1)`
`        ``return` `base;`

`    ``unsigned ``long` `long` `int` `temp = modPow(base, exponent/2);`

`    ``if` `(exponent %2 ==0)`
`        ``return` `(temp%MOD * temp%MOD) % MOD;`
`    ``else`
`        ``return` `((( temp%MOD * temp%MOD)%MOD) * base%MOD) % MOD;`
`}`

`// A Function to calculate Modulo Multiplicative Inverse of 'n'`
`unsigned ``long` `long` `int` `findMMI(unsigned ``long` `long` `int` `n)`
`{`
`    ``return` `modPow(n, MOD-2);`
`}`

`// A Function to calculate the prefix hash`
`void` `computePrefixHash(string str, ``int` `n, unsigned ``long` `long`
`                       ``int` `prefix[], unsigned ``long` `long` `int` `power[])`
`{`
`    ``prefix[0] = 0;`
`    ``prefix[1] = str[0];`

`    ``for` `(``int` `i=2; i<=n; i++)`
`        ``prefix[i] = (prefix[i-1]%MOD +`
`                    ``(str[i-1]%MOD * power[i-1]%MOD)%MOD)%MOD;`

`    ``return``;`
`}`

`// A Function to calculate the suffix hash`
`// Suffix hash is nothing but the prefix hash of`
`// the reversed string`
`void` `computeSuffixHash(string str, ``int` `n,`
`                       ``unsigned ``long` `long` `int` `suffix[],`
`                       ``unsigned ``long` `long` `int` `power[])`
`{`
`    ``suffix[0] = 0;`
`    ``suffix[1] = str[n-1];`

`    ``for` `(``int` `i=n-2, j=2; i>=0 && j<=n; i--,j++)`
`        ``suffix[j] = (suffix[j-1]%MOD +`
`                     ``(str[i]%MOD * power[j-1]%MOD)%MOD)%MOD;`
`    ``return``;`
`}`

`// A Function to answer the Queries`
`void` `queryResults(string str, Query q[], ``int` `m, ``int` `n,`
`                  ``unsigned ``long` `long` `int` `prefix[],`
`                  ``unsigned ``long` `long` `int` `suffix[],`
`                  ``unsigned ``long` `long` `int` `power[])`
`{`
`    ``for` `(``int` `i=0; i<=m-1; i++)`
`    ``{`
`        ``int` `L = q[i].L;`
`        ``int` `R = q[i].R;`

`        ``// Hash Value of Substring [L,R]`
`        ``unsigned ``long` `long` `hash_LR =`
`            ``((prefix[R+1]-prefix[L]+MOD)%MOD *`
`             ``findMMI(power[L])%MOD)%MOD;`

`        ``// Reverse Hash Value of Substring [L,R]`
`        ``unsigned ``long` `long` `reverse_hash_LR =`
`            ``((suffix[n-L]-suffix[n-R-1]+MOD)%MOD *`
`             ``findMMI(power[n-R-1])%MOD)%MOD;`

`        ``// If both are equal then the substring is a palindrome`
`        ``if` `(hash_LR == reverse_hash_LR )`
`        ``{`
`            ``if` `(isPalindrome(str, L, R) == ``true``)`
`                ``printf``(``"The Substring [%d %d] is a "`
`                       ``"palindrome\n"``, L, R);`
`            ``else`
`                ``printf``(``"The Substring [%d %d] is not a "`
`                       ``"palindrome\n"``, L, R);`
`        ``}`

`        ``else`
`            ``printf``(``"The Substring [%d %d] is not a "`
`                   ``"palindrome\n"``, L, R);`
`    ``}`

`    ``return``;`
`}`

`// A Dynamic Programming Based Approach to compute the`
`// powers of 101`
`void` `computePowers(unsigned ``long` `long` `int` `power[], ``int` `n)`
`{`
`    ``// 101^0 = 1`
`    ``power[0] = 1;`

`    ``for``(``int` `i=1; i<=n; i++)`
`        ``power[i] = (power[i-1]%MOD * p%MOD)%MOD;`

`    ``return``;`
`}`