2

Note that any hash algorithm can be used to break files into chunks where chunk boundaries don't change much after inserts/deletes. Rabin fingerprinting (and RabinKarp rollsums) are just hash functions that are good for this purpose. The trick is you calculate the hash of a small window of data bytes (say 64 bytes, but I've heard even as low as 16 works ...


1

Running birthday attack should be faster than writing the question: sqrt(1e12) = 1e6 Also note that your question have nothing with rolling hashes, moreover, with rolling hash len(s) is fixed. So it may be that you missed some condtitions from the original question.


Only top voted, non community-wiki answers of a minimum length are eligible