Wednesday, December 5, 2012


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({Si to Sj})=(Sia0+Si+1a1+Si+2a2...)%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({Si to Sj}) to be computed from Hash({Si-1 to Sj-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.


No comments:

Post a Comment