You might misunderstand my idea. My run time is independent to the string content.andresw1 wrote:You have very nice idea but I have some doubts that this will give TLE. After you find the same hash as the patern you will need to do the slow compare to see if the matching is valid. For the test case that krijger mentioned (a lot of 'A's) this will give TLE. Do you do something else which I missed? Do you have AC?
david wrote:Cho wrote:Let c[j] be the character of the shorter string, I define its hash value as:
Summation over all valid i,j: c[j] * (3 ^ (i*100+j)) mod 2^32
(x^y denotes x to the power y instead of bitwise-XOR.)
Are you sure you didn't mean, for example,
c[j] * (32 ^ (i*100+j)) mod 2^32 ?
The hash function you wrote will fail to return different values for such simple strings as "ab" and "da" (assuming a is coded as 0), so I can't believe you got AC doing that without later checking if the match is exact (in which case you should get TLE for cases where both the matrix and the pattern are full of a's, for instance).
Yes, you are right. I should use 27 instead of 3. Forfunately, there are only 15 test cases. And my bug can only be caught if you decide one for it specifically.
david wrote:I tried to use as a hash funtion the summation over all valid i, j of
c[j] * (32 ^(i * pattern width + j)) mod 1000000007,
but I got WA after 9.7s, so even if this approach can be made to work I wonder how you managed to get it accepted in about 2.5 seconds.
I just tried your method and got AC in 7 secs. Make sure your arithmetic part is computed correctly.