Equal pieces
A proofreader is preparing a new edition and checking repeats: in a novel the same phrase may occur in different chapters, and it matters that it is typeset identically in both places. The layout program asks questions of the form “do the len characters starting at position a match the len characters starting at position b?”. There are many questions, and pieces can be tens of thousands of characters long, so comparing them letter by letter takes too long.
Answer all the questions. The tests include the opening of War and Peace and a Thue–Morse string of 65,536 letters a and b.
Input
The first line holds the text: n characters (1 ≤ n ≤ 100,000), any except a line break, including Cyrillic letters and spaces. The second holds the number of questions q (1 ≤ q ≤ 100,000). Then q lines of three numbers a, b, len: positions are counted in characters from zero, len ≥ 1, a + len ≤ n and b + len ≤ n.
Output
q lines: yes if the pieces match, and no if not.
Examples
Example 1
абракадабра 6 0 7 4 1 8 3 0 5 3 0 3 1 0 0 11 0 5 6
yes yes no yes yes no
Example 2
abbabaabbaababba 4 0 8 8 0 12 4 3 11 2 0 6 3
no yes no yes
Limits
- Time · Python
- 4000 ms
- Time · Go
- 1000 ms
- Memory
- 256 MB
- Judging
- 8 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
Compute once the hashes of all prefixes of the text and the powers of the base. Then the hash of any piece is one multiplication and a subtraction, and a question costs O(1).
2Hint 2
Which modulus to take? A hash without a modulus, with 64-bit overflow, seems reliable: 18 quintillion values. Look at the fourth test: in a Thue–Morse string the 1024-letter pieces starting at positions divisible by 1024 come in two kinds.
3Hint 3
Different 1024-letter Thue–Morse pieces get the same hash modulo 2⁶⁴ for any odd base: that is the theorem from the article. A prime modulus is needed, and the base is best chosen at random at start-up.
4The idea
A polynomial hash modulo the prime 2⁶¹ − 1 with a random base. The prefix hashes H[i] and the powers bi are computed in O(n), and the hash of the piece [a, a + len) is H[a + len] − H[a] · blen modulo it. A “yes” for different pieces is possible, but with a random base the probability of such an error is at most (len − 1)/p, and below 10⁻⁸ for all the questions together.
5Walkthrough
In Python the remainder modulo 2⁶¹ − 1 is computed with built-in long integers. In Go the product of two residues takes up to 122 bits: it is taken from bits.Mul64, and the remainder from bits.Div64. The base is chosen by a random number generator on every run, so no test prepared in advance knows which strings will collide for it.
Why not 2⁶⁴? The difference of the hashes of the Thue–Morse strings Sk and Tk is −(b − 1)(b² − 1)…(b2k−1 − 1), and for odd b it has at least 1 + (k − 1)(k + 4)/2 factors of 2. For k = 10 that is 64: 1024-letter pieces, one of which is S₁₀ and the other T₁₀, get one hash. The fourth test has 40,000 questions about such pieces, and a solution with overflow answers “yes” to all of them.
5+Solution
6Complexity
O(n + q) time and O(n) memory. Comparing letter by letter would cost O(q · len), up to 10⁵ · 10⁵ = 10¹⁰ comparisons on a text of a single letter.
7Common mistakes
- Overflow instead of a modulus.
unsigned long longin C++,uint64in Go without a remainder, or& (2**64 − 1)in Python is the modulus 2⁶⁴, and Thue–Morse strings break it for any odd base, while for an even one identical last 64 letters are enough. - A small modulus. Modulo 10⁹ + 7 a single comparison errs with probability about len/10⁹: over a hundred thousand questions about pieces thousands of characters long, that becomes noticeable. Take 2⁶¹ − 1 or two moduli.
- A negative remainder. H[a + len] − H[a] · blen can be negative. In Python
%returns a non-negative number, in Go and C++ it does not: add the modulus before taking the remainder. - Bytes instead of characters. Positions in the statement are counted in characters, and a Cyrillic letter in UTF-8 is two bytes. In Go convert the string to a slice of runes.