The longest common piece
The scenes of this catalogue are written by different authors, and sometimes a function moves from file to file by copying. Before moving shared code into a library, we would like to find the longest piece that occurs in both files. Copy finders such as PMD CPD and jscpd compare files with a Rabin–Karp rolling hash; do the same for two texts.
Find the longest piece that occurs both in the first text and in the second: consecutive characters, not a subsequence. The tests include real pairs of the catalogue’s scene files with spaces and line breaks squeezed into one space, two excerpts of War and Peace, and the genomes of the phages λ and φX174.
Input
Two lines: the texts s and t, from 1 to 50,000 characters each. The characters may be anything except a line break, including Cyrillic letters and spaces; lengths and positions are counted in characters.
Output
The length L of the longest common piece. If L > 0, then after a space the positions i and j at which it starts in s and in t (from zero): s[i..i + L) = t[j..j + L). If there are several such places, any will do. If there are no common characters, print 0.
Examples
Example 1
абракадабра кадабракадабр
10 0 3
Example 2
кот пёс
0
Limits
- Time · Python
- 5000 ms
- Time · Go
- 1000 ms
- Memory
- 256 MB
- Judging
- 13 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
Suppose you can quickly answer the question “is there a common piece of length L?”. How do you find the largest L without trying all lengths in a row?
2Hint 2
If there is a common piece of length L, there is also a common piece of length L − 1: its beginning. So the answer is “yes” up to some length and only “no” after it, and binary search finds the boundary.
3Hint 3
How do you answer the question for one length in linear time? Put the hashes of all windows of length L of the first text into a table and roll a window of the same length along the second text: that is Rabin–Karp with all the patterns at once.
4The idea
Binary search on the length L, and inside it a check in O(n + m): the hashes of the windows of s of length L go into a hash table, and the windows of t are looked up in it in turn. A window’s hash is taken from the prefix hashes in O(1). A hash match is checked by comparing strings, so the answer is never false, and a random base modulo the prime 2⁶¹ − 1 keeps a prepared test from causing extra checks.
5Walkthrough
The prefix hashes of both texts and the powers of the base are computed once. For a length L a dictionary “hash of a window of s → its position” is built; then for each window of t we see whether its hash is in the dictionary, and if it is, compare letters. The first real match gives the positions. The binary search runs over L from 0 to min(n, m) and remembers the positions of the last successful length.
Look at the answers of the third test: the files dynamic-programming-intro.js and dijkstra.js share a piece of 528 characters, almost the whole function marker, which draws a circle with the start or finish letter on a map: it was copied from one scene into the other. In the excerpts of War and Peace the longest common piece is 33 characters, and in two random strings of a and b of 50,000 letters each it is 30, about 2 log₂ 50,000: that much of random strings matches purely by chance.
5+Solution
6Complexity
O((n + m) log min(n, m)) on average: seventeen passes over a hundred thousand windows. The textbook table of longest common suffixes is O(n · m), 2.5 billion cells. A linear solution exists as well, via a suffix automaton or a suffix array with an LCP array, but binary search with a hash takes ten minutes to write.
7Common mistakes
- An n × m table. Correct, but too slow: in Python even 10⁸ cells take minutes.
- A subsequence instead of a piece. The longest common subsequence allows gaps; here the characters must be consecutive.
- No letter check. If you trust a hash match, with an unlucky modulus the binary search may climb on a false “yes” and output a length that does not exist. With the check, a “yes” is always honest.
- A hash with 64-bit overflow. The eleventh test holds two halves of the Thue–Morse string: they have many different pieces whose hashes modulo 2⁶⁴ coincide for any odd base. Without a check that is a wrong answer, with a check extra work.
Algorithms behind it
O(n + m) on average
1 problem
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
SRT
Technique
Binary search on the answer
If checking an answer is easier than finding it, and the check is monotone, search for the answer by halving.
O(log D · cost of a check)
2 problems