The comparison counter
In October 2020 a Python user reported that bytes.find hangs on a file of the bytes 00 and FF: searching for a run of 15,403,807 FF bytes finished instantly, and a run one byte longer did not finish at all. The developers want a tool that says in advance how much work a search will do, without running it.
Take the search from the article. A pattern of length m is laid against a text of length n at each shift s = 0, 1, …, n − m, and letters are compared from left to right: text[s] with pattern[0], text[s + 1] with pattern[1] and so on, until the first mismatch or the end of the pattern. Each comparison of two letters, whether they match or not, costs one. The search does not stop at the first occurrence: it goes through all the shifts.
For the text «колокол» and the pattern «кол» this is 3 + 1 + 1 + 1 + 3 = 9 comparisons. Compute the answer for texts of up to a hundred thousand letters. Simply running the search will not do: on an unlucky text it would make billions of comparisons, and catching exactly such texts is the tool’s job. The tests include the beginning of War and Peace, the genome of phage λ and a reduced copy of that very file, with the letters x and y instead of the bytes 00 and FF.
Input
Two lines: the text and the pattern. They may contain any characters except a line break and the null byte, including Russian letters and spaces; the lines do not start or end with a space. Length is counted in characters: 1 ≤ m ≤ n ≤ 100,000.
Output
One number: how many letter comparisons the search will make.
Examples
Example 1
колокол кол
9
Example 2
aaaaaaaa aaab
20
Limits
- Time · Python
- 4000 ms
- Time · Go
- 1000 ms
- Memory
- 256 MB
- Judging
- 12 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
How many comparisons does one shift cost? It depends on just one number: how many letters of the pattern in a row match the text starting from position s.
2Hint 2
Let k be the length of the common prefix of the pattern and the piece of text from position s. If k < m, the shift compared k matched letters and one mismatched: k + 1. If k = m, there are exactly m comparisons. It remains to find k for all s at once, faster than by comparing.
3Hint 3
Glue together the pattern, a separator not found in the strings, and the text. For each position of the glued string the length of its common prefix with the whole glued string is needed. Such an array is called the Z-function and is computed in linear time.
4The idea
The cost of shift s is min(ks + 1, m), where ks is the length of the common prefix of the pattern and the text from position s. All the ks are given by the Z-function of the string p + “\0” + t: at position m + 1 + s it equals exactly ks, and the separator keeps the common prefix from running past the end of the pattern. The search is not run at all: the answer is assembled from the numbers it would have obtained.
5Walkthrough
The Z-function is computed from left to right. Keep the rightmost window [l, r) known to match the beginning of the string. For a new position i inside the window the start of the match can be taken from the already computed z[i − l], cut off at the edge of the window, and only then letters are compared further. Each successful comparison moves the right edge of the window, so there are at most as many of them as the length of the string.
Look at the answers. On the beginning of War and Peace searching for «князь Андрей» costs 103,196 comparisons over 99,967 shifts, a little over one per shift. On a text of nothing but a’s with the pattern a…ab, 2,500,050,000: each of the 50,001 shifts costs all 50,000 comparisons. In the copy of the file of 00 and FF the bytes are replaced by the letters x and y, a run of 40,000 letters y stands in the middle of random text, and the pattern is one letter longer than the run. The answer is 750,104,190, and almost all of it goes on shifts inside the run: each goes through its remainder to the end.
5+Solution
6Complexity
The Z-function is O(n + m) time and memory, the sum O(n). Running the search directly is O(n · m), 2.5 billion comparisons in the sixth test. The Z-function can also be done without: the length of the common prefix of two strings is found by binary search, comparing pieces with a polynomial hash in O(1). That is O(n log m) with a small probability of error.
7Common mistakes
- Running the search and counting. The answer is correct, but on a text of nothing but a’s the work is quadratic, the very work the tool is meant to predict without doing.
- Forgetting the mismatched letter. A shift on which k < m letters matched costs k + 1 comparisons, not k: on «колокол» you get 6 instead of 9.
- An extra comparison on an occurrence. If all m letters matched, there is nothing more to compare: m, not m + 1.
- Gluing without a separator. The common prefix can run from the pattern into the text, and k comes out greater than m.
- A 32-bit counter. The answer reaches 2.5 · 10⁹ and does not fit in
int32. - Bytes instead of characters. In Go a string is UTF-8 bytes, and «колокол» has 14 of them. Count in runes, or there will be twice as many shifts as characters.
Algorithms behind it
O(n · m)
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