Hashing

Hashing is an very interesting topic in competitive programming.Using memory we can efficient our program and that's called Hashing.

We are talking about string processing using Hashing.

 Hash Function: The concept of number system is used for hash function. Suppose, you are given 5, 2 ,5, 2 and asked to make it 5252. You can easily do it.
                                                                0 * 10 + 5      =  5           H[1] = 5
                                                                1 * 10 + 2      =  52         H[2] = 52
                                                                12 * 10 + 5    =   525      H[3] = 525
                                                                125 * 10 + 2  =   5252    H[4] = 5252
Suppose, our string is "abcb". Now, we need to select a base number.Here, an unknown prime number is used for base number. We use 3797 as base number.

1. #define ULL   unsigned long long
3. const int N = 1000007;  // size of the string
4. const ULL hs = 3797;    // base value
6. ULL F[N], H[N], R[N];
8. char text[N], pat[N];
9. 
   
10.  H[0] = 0;   // below calculation like number system
12.  for (int i = 0; i < n; i++) {
13.       H[i + 1] = H[i] * hs + text[i];
14.  } 

 5252 is not a palindrome  number however, 252 is palindrome number.5252 - 5000 = 252 by this way get 252.Now build a function for getting substring.
 

1. F[0] = 1; // here calculation of power of base number.
2. for (int i = 1; i < N; i++) {
3.      F[i] = F[i - 1] * hs;
4. }
5. // This is the function for getting substring
6. // x is left pointer and y is right pointer of the substring
7. ULL seg(int x, int y)
8. {
9.     return H[y] - F[y - x + 1] * H[x - 1];
10. }

   Here , H[y] contains hash summation of 1 to y index.It looks like, H[y]=5252. Now we need              subtract 5000 and it means 10^3. In 5252 we want to get 252 so, y = 4 and x = 2. .F[N] contains          the  power of  base number.So,
   F[y-x+1] = F[4-2+1] = 1000 and H[x-1] = H[2-1]=5.
   H[4] - F[3]*H[1] = 5252 - 5000 = 252.
  This is the calculation inside the function.


1) You are given a string, text = "ababab", another string pattern = "ab".How many times pattern occurs in text. Here, 3 times. Both of the string size is 10^5 and query 10^2.This problem looks like
Light 1255 - Substring Frequency

We can easily solve this problem using hashing.(Solution)

2) You are given a string, st = "ammommb". You have to say what is size of largest palindromic substring of the given string. Here, mmomm = 5. String size 10^5 and query 10^2. We need forward hashing and reverse hashing for checking Palindrome. Also, we need two binary search for even length and odd length of the palindrome.
This problem looks like Spoj LPS (Solution)

3) Light 1258 - Making Huge Palindromes
4) Toph - Palindromic Naming Convention

I believe that you can solve both problems.Those problems can be solved by same idea.

Special thanks to Fahim Shahriar Shakkhar