Hashing

Source :

Link1 Link2 Link3

Code :

Application :

1. Given a text and a pattern. Find all occurrences of the pattern.

:: Check all sub-strings of length |pattern| in text & compare hash value in O(|text| + |pattern|).

2. Given two string S1 & S2. Find longest common sub-string between them.

:: Binary search on length and check them with Hash value.

3. Find lexicographic minimal cyclic shift of a string of length n.

:: See this.

4. Given a string S. Find a smallest period in it.

 :: Let answer will be of length X and it will divide |S|. Then we will check Hash value of S[0...n-x-1] & S[x...n-1] are equal or not.

5. Given two trees. Check if they are isomorphic or not.

:: Read this.

6. Read this also.

Problem :

1. NHAY - A Needle in the Haystack

2. ADAPHOTO - Ada and Terramorphing (10^6 version)

3. 1517. Freedom of Choice (10^5 version)

4. Minimal Rotation

5.  C. Watto and Mechanism

6. D. Palindrome pairs

7. E. Games on a CD

*** Solve all problems mentioned in CP algo.