A run that must stay unbroken
Same match-or-not table, but a mismatch resets to zero instead of borrowing a neighbour. About 11 minutes.
No gaps this time
A substring is a solid chunk of letters with no gaps. "abcdxyz" and "xyzabcd" share "abcd", four letters in a row. This is what a plagiarism checker looks for: long stretches copied word for word.
The grid idea still works, but each box now means something stricter: how long is the matching chunk that ends exactly at these two letters? The moment two letters differ, no chunk can end there, so the box is 0.
- best
- 1
Row 'a': it matches the 'a' in column 4, so a run of 1 starts there. Every mismatch is 0: a broken run is worth nothing.
The best chunk can end anywhere
With subsequences, the answer always sat in the bottom-right corner. Not here. The longest chunk might end in the middle of both words and be followed by nothing in common.
So keep a running record as you fill the grid: the biggest number you've written anywhere. In the example, "abcd" builds a diagonal 1, 2, 3, 4, while "xyz" only reaches 3.
if a[i - 1] == b[j - 1]:
run[i][j] = run[i - 1][j - 1] + 1
else:
run[i][j] = 0 # the run breaksTwo letters don't match. The chunk ending just before both of them was 4 long. How long is the chunk ending at these two letters?
- A0
- B5
- C4
Show the answer
0. A mismatch breaks the chunk. No chunk can end on two different letters.
Longest common substring
You get two strings a and b. Return the length of their longest common substring: the longest block of letters that appears, unbroken and in the same order, in both strings.
a = "abcdxyz", b = "xyzabcd" → 4
0 ≤ a.length, b.length ≤ 1,000 · lowercase English letters