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

_{i}a

^{0}+S

_{i+1}a

^{1}+S

_{i+2}a

^{2}...)%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:

## No comments:

## Post a Comment