The client-server file synchronization program, rsync, compares two versions of a file (typically on different machines) and updates one copy to be identical to the other, hopefully only transferring the part that is different. The section of the algorithm that looks for differences works roughly like this:

The server computes a checksum for each disjoint 512-byte block of its copy of the file: b(1, 512), b(513, 1024), b(1025, 1536), etc. It sends this short list of checksums to the client.

The client computes every 512-byte checksum for its copy of the file: b(1, 512), b(2, 513), b(3, 514), b(4, 515), etc. The client's list of checksums is generally longer than the file itself!

The client now looks for 512-byte blocks in the server's copy that might be present in the local copy. The idea is that if a checksum matches, the blocks might be identical, but if the checksums don't match, the blocks are surely not identical.

Describe an algorithm, given the above two lists of blocks, that comes up with a list of blocks on the server for which no block on the client can possibly match.