Edit Question - KnowledgeHub

Title Body

Summary: Suppose I have an unsigned int number. Then I multiply it several times(and there's overflow, which is expected ). Then is it possible to "revert" the original value back? In details: It's all about Rabin-Karp rolling hash . What I need to do is: I have the hash of a long string - for example: "abcd". Then I have the hash for a shorter substring - for example "cd". How to calculate the "ab" hash with O(1), using the two given hashes? What I have now as an algorithm: substract the "cd" hash from "abcd" hash (remove the last elements from the polynomial) devide the "abcd" hash by p ^ len( "cd" ) , where p is the base (prime number). So this is: a * p ^ 3 + b * p ^ 2 + c * p ^ 1 + d * p ^ 0 - abcd c * p ^ 1 + d * p ^ 0 - cd ab gets: ( ( a * p ^ 3 + b * p ^ 2 + c * p ^ 1 + d * p ^ 0 ) - ( c * p ^ 1 + d * p ^ 0 ) ) / ( p ^ 2 ) = a * p ^ 1 + b * p ^ 0 And this works, if I don't have an overflow (if p is small number). But if it's not - it's not working. Is there any trick or something? P.S. The c++ tag is because of the number's overflow, as it is specific (and different from python, scheme or sth)

Tags (comma-separated) Cancel