SPOJ PLD

Link : PLD

Category : Hashing

Hint : Consider substrings of S of length k and substrings of Reverse(S) of length k. If the hash value of one substring of S matches with hash value of substring of Reverse(S), and second starts when first ends, there is a match!

Solution : Well, the hint says pretty much all of it, except for a good hash function. For hash value of substring Si to Sj, we better not take O(k) time (else program is O(N*K) and gets TLE), hence I used the polynomial hash function

Hash({S_i to S_j})=(S_ia⁰+S_i+1a¹+S_i+2a²...)%p
Where a and p were primes (p was because of good hash spread, a was for no good reason :D ). This hash function allows Hash({S_i to S_j}) to be computed from Hash({S_i-1 to S_j-1}) in O(1) time, giving the complexity of hashing all substrings of S of length k O(N).

To do the index match (S's substring ends where Reverse(S)'s starts), keep a sorted vector at all hash values, and so a binary search.

Code: