Old blocks in a new file
The receiver has the old version of a file, the sender the new one. The receiver cuts the old version into blocks of B bytes: block 0 is bytes 0 to B − 1, block 1 the next B bytes, and so on; the last block may be shorter. The sender walks along the new version from left to right, starting at position i = 0, and at each step looks at the piece of the new version from position i of length L = min(B, the bytes left to the end):
- if this piece exactly matches some block of the old version (the same length and byte for byte), the sender reports the block number and moves to position i + L;
- otherwise it sends the byte at position i as it is and moves to i + 1.
Count how many blocks will be found, how many bytes will be sent as they are, and into how many continuous pieces these bytes split (a piece is bytes sent in a row, with no block found between them). Three tests are real edits of a chapter of this site’s basic course; line breaks in them are replaced by spaces.
Input
The first line holds the block size B. The second holds the old version, the third the new one: byte sequences from 1 to 400,000 long, without line feed (10) or carriage return (13) bytes. 1 ≤ B ≤ 400,000.
Output
Three numbers separated by spaces: the number of blocks found, the number of bytes sent as they are, and the number of pieces they split into.
In the first example the old version is cut into the blocks “the ”, “quic”, “k br”, …, “azy ”, “dog”. In the new one “so ” is inserted before “the”, and all the blocks shift by three bytes, but the sender finds them at their new places; at the end “cat” replaces “dog”, three bytes. In the second example the block “abc” occurs twice in the old version, and the short last block “ab” matches the end of the new version.
Examples
Example 1
4 the quick brown fox jumps over the lazy dog so the quick brown fox jumps over the lazy cat
10 6 2
Example 2
3 abcabcab xabcab
2 1 1
Limits
- Time · Python
- 6000 ms
- Time · Go
- 1500 ms
- Memory
- 256 MB
- Judging
- 10 tests
Walkthrough
Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.
1Hint 1
Checking whether a piece is among the blocks is easy: put the old version’s blocks into a hash table by content. But for that the piece must be cut out and hashed, L bytes at every position. What does that cost if there are no matches and the blocks are two hundred thousand bytes each?
2The idea
On a one-byte step the piece changes by two bytes: one leaves on the left, another arrives on the right. We need a sum that can be shifted the same way in O(1). rsync’s weak sum from the article, a = Σx and b = Σ(L − k)·xk modulo 216, shifts by two formulas: a ← a − xleft + xarrived, b ← b − L·xleft + a. The polynomial hash from the article on the polynomial hash works too. The sum serves as a filter: a piece is cut out and compared with the blocks only when its sum matches the sum of some block.
3Walkthrough
First go through the old version: put each block into a hash table by content, and its pair (a, b) into a set. Then walk the new version. Compute the sum of the piece at position i afresh only when it is “fresh”, at the start and after a block is found; after that, roll it. If the pair of sums is in the set, cut out the piece and look it up in the table: found means a block, jump L; not found means a false alarm, and the byte goes as it is.
The end of the file needs care. When fewer than B bytes remain, on a shift the piece not only loses a byte on the left but gains nothing on the right: L decreases by one. The formulas for this case are a ← a − x, b ← b − L·x: the departing byte had weight L, and the others’ weights do not change. This way the old version’s short last block is found at the very end of the new one, and only there: a piece shorter than B occurs only at the end of the file (tests 7–9).
On the edit of the chapter’s description (the third test) 139 blocks out of 140 are found: one edit at the start shifted everything else by a hundred-odd bytes, but the blocks were found at their new places, and 598 bytes went as they are.
3+Solution
4Complexity
O(|old| + |new|) for the sums and their shifts, plus cutting out a piece for each matching sum. Real matches cost O(|new|) in total, since each block found consumes its bytes. False alarms on 32 bits of sums are rare: on the article’s chapter edit there are none at all.
5Common mistakes
- Looking for blocks only at boundaries. If after a miss you jump straight B bytes, or compare blocks at the same positions, one insertion at the start hides all the blocks after it. The first example already fails this way.
- Cutting out the piece at every position. The answer is correct, but it is O(|new|·B): about sixty billion bytes on the sixth test.
- The window at the end of the file. If you assume the piece is always B long, the short last block will never be found, and the sums at the end will be wrong.
- A negative remainder. In Go and C the remainder of a negative number is negative: after subtracting, bring the sum back into [0, 216).
Algorithms behind it
O(n + m): the window sum shifts in O(1), the strong sum only on a weak match
2 problems
STR
Technique
Polynomial hash
The hash of any piece of a string in O(1) from prefix hashes: comparing substrings, windows, common prefixes, with a bound on the error probability.
O(n) preparation, O(1) per piece hash
2 problems