Longest common substring and rolling rows in Python

Why it matters

Finding the longest shared run of text is a common task. A plagiarism checker looks for long blocks of words that two documents share. A tool that compares two versions of a file looks for long unchanged stretches. A program that compares two DNA sequences looks for long regions where both strings match letter for letter. In each case the answer is one unbroken block of letters, not a set of letters scattered through both strings.

This lesson builds the method in two steps. The first step fills a full table, so you can see how each answer depends on a smaller answer. The second step notices that each row needs only the row above it. Once you see that, you can keep two rows instead of the whole table. This is the rolling rows idea. For a pair of long strings, the full table keeps thousands of rows and the rolling version keeps two.

You should know the DP recipe from the first lesson of this module: a table, a base case and a recurrence. You should be able to read s[i] in Python, which gives the letter at index i. Indexes start at 0, so the first letter is at index 0. A list is an ordered group of values written with square brackets, such as [0, 0, 0]. A slice is a piece of a string or a list, written s[start:end]. The longest common subsequence lesson earlier in this module uses a close relative of this table. This lesson changes one rule, and that one change changes the problem.

The programs in this lesson were run with Python 3.14.4. Each one is a complete file. Save it as main.py and run it with python3 main.py.

Substring is not subsequence

A substring is a block of letters that sits together in the original string. Nothing is removed from the middle. A subsequence keeps the order of the letters but may skip any of them.

Take the strings abxcdy and abcdz. The longest common substring has length 2. The blocks ab and cd each appear in both strings as unbroken pieces, and no block of length 3 does. The longest common subsequence has length 4, because abcd appears in both strings if you skip the x and the final y in the first one.

The single word "substring" makes the difference. The same two strings give an answer of 2 or 4, depending on that word. Read each problem statement with this in mind.

The idea: a run that ends at each cell

The table has one row for each prefix of the first string and one column for each prefix of the second string. Row 0 and column 0 stand for the empty prefix, which is a string with no letters. This is the same layout the longest common subsequence lesson used.

In Python the table is a list of lists. The line dp = [[0] * (m + 1) for _ in range(n + 1)] builds n + 1 rows, and each row is a new list of m + 1 zeros. The mistakes section shows why each row has to be built separately.

The state is dp[i][j]. It holds the length of the longest common run of letters that ends exactly at position i - 1 in the first string and at position j - 1 in the second string. The word "ends" is the key. The run must finish on those two letters. If those two letters differ, no shared run can finish there, so the value is 0.

The recurrence, for i and j starting at 1:

• If a[i - 1] equals b[j - 1], the run can grow by one letter. It grows from the run that ended one step back in each string. That run sits in the cell diagonally up and to the left, so dp[i][j] = dp[i - 1][j - 1] + 1.
• Otherwise the run is broken, so dp[i][j] = 0.

The longest common subsequence lesson took the larger of the cell above and the cell to the left on a mismatch. This lesson writes 0 instead. A substring cannot skip letters, so a mismatch ends every run that was going through that cell.

The answer is not the last cell in the table. A run can end anywhere, so the answer is the largest value anywhere in the table. The program keeps that largest value as it goes.

A small example

Take a = "xaby" and b = "zab". The strings are short enough to draw the whole table. The program below prints it. Each printed line is one row of the table, and the first line is row 0, the empty prefix of a.

The output is:

[0, 0, 0, 0]
[0, 0, 0, 0]
[0, 0, 1, 0]
[0, 0, 0, 2]
[0, 0, 0, 0]
length = 2
text = ab

Walk through the two non-zero cells. Row 2 is the letter a from xaby, and column 2 is the letter a from zab. They match. The cell diagonally up and to the left is 0, so this cell is 0 + 1 = 1. Row 3 is the letter b and column 3 is the letter b. They match. The diagonal cell, row 2 and column 2, holds 1, so this cell is 1 + 1 = 2. Every other cell is a mismatch and holds 0.

The largest value is 2, in row 3. That row is the end of the run, counted in letters of a, so the run ends after index 2 of xaby. Its length is 2, so it starts at index 1 and is ab.

The slice a[best_end - best:best_end] gives the letters from index start up to, but not including, index end. Here end is best_end, which is 3, and start is best_end - best, which is 1. So a[1:3] gives ab. A slice that stops at end leaves out the letter at end, which is why the slice needs no + 1. If you know Java, this does the same job as substring.

The variable best_end stores i at the moment the best run was found. It is the row number, not an index, and that is why it works as an exclusive end.

Keeping two rows

Look at the recurrence again. Cell dp[i][j] reads one cell from an earlier row: dp[i - 1][j - 1], the cell in the row directly above it. It never reads a row two steps back. So once row i is finished, every row above i - 1 is never read again. Only the row directly above matters.

The rolling rows method uses two lists of length m + 1. The list prev holds row i - 1. The list curr is filled with row i. When row i is complete, the program swaps the two names. A name is a label that points at a list. The line prev, curr = curr, prev makes prev point at the finished row and curr point at the old prev list, which is reused for the next row. The right side is built first, so the swap needs no third variable, and it changes only the two labels, not the numbers inside the lists.

Here is the rolling version, run on hellomoon and moonhello.

The output is:

length = 5
text = hello

The line curr[0] = 0 keeps column 0 at 0. Column 0 stands for the empty prefix of b, and an empty prefix shares no run with anything.

The else branch matters more than it looks. After the first swap, curr is the list that held row i - 2. Its old numbers are still inside it. A mismatch must write a 0 over those old numbers. If the else branch is missing, the program reads a leftover value on the next row. The mistakes section below shows the wrong output this causes.

Following the two rows

Take xaby and zab again, and print the list curr after each pass. The program is the rolling version with the best-run tracking removed, so it only shows the rows.

The output is:

row 1 (x): [0, 0, 0, 0]
row 2 (a): [0, 0, 1, 0]
row 3 (b): [0, 0, 0, 2]
row 4 (y): [0, 0, 0, 0]

Row 2 is the first row with a match. The letter a matches column 2, and the list prev holds row 1, where column 1 is 0, so the value is 0 + 1 = 1. Row 3 reads row 2 at column 2, which is 1, and adds 1 to give 2. Row 4 has no match, so every value is 0. At the end of each pass, the program swaps the two names, so the row that was just written becomes prev for the next pass.

Each row is correct on its own, and no row needed anything older than the row before it. The best value, 2, was recorded during row 3.

The memory saving

Python lists do not store numbers in a packed block the way a C array does. Each slot holds a pointer to a number object, and the list has a header. On the machine used for this lesson, sys.getsizeof([0] * 5001) returns 40064 bytes. That figure counts the list, not the numbers it points to, and the numbers in this table are often shared small objects. A full table for two strings of 5,000 letters has 5,001 such rows, which is about 200 MB. Two rows take about 80 KB. The numbers in the table can take extra room when they are not shared, so the real total is a little higher. The exact sizes depend on the Python build and the machine.

The number of steps is the same in both versions, about the length of one string times the length of the other. The rolling version saves memory and does not save time.

One array is enough

Two rows can be cut to one list. The trick is the order in which the columns are filled.

When the program writes dp[j], it reads dp[j - 1]. If the columns go from left to right, dp[j - 1] was already overwritten with the current row, so the read gets a value from the wrong row. If the columns go from right to left, dp[j - 1] has not been written yet in this row. It still holds the value from the row above, which is exactly the value the recurrence needs.

The loop for j in range(m, 0, -1): counts from m down to 1. range takes a start, a stop that is not included, and an optional step. The step -1 makes the count go down.

The output is the same as before:

length = 5
text = hello

This version is the shortest. The two-row version is easier to read at first, so it is a good first step. Both need the same reset to 0 on a mismatch.

Common mistakes

Leaving out the reset on a mismatch

With two rows, the else branch is the only line that clears old numbers. Delete it and the program gives wrong answers on some inputs. The next program is the rolling version with the else branch removed, run on abba and aa.

Its output is:

length = 2
text = ba

The text ba does not appear in aa, so the output contradicts itself. The correct answer is length 1, with the text a. The two b rows in the middle do not clear their list, so the 1 from the first row stays in it. The last a reads that leftover 1 and adds one to it, giving 2. The fix is the else branch that writes 0.

Taking the larger neighbour, as in the subsequence lesson

On a mismatch, the subsequence recurrence takes max(dp[i - 1][j], dp[i][j - 1]). Copying that rule into this problem gives the wrong kind of answer. On abxcdy and abcdz it returns 4, which is the length of the subsequence abcd, not the length of the substring. Read the problem word first, then pick the rule.

Reading the answer from the last cell

The answer is the largest value in the table, not dp[n][m]. Here is a program that prints only the last cell for hellomoon and moonhello.

Its output is dp[n][m] = 0. The last letter of hellomoon is n, and the last letter of moonhello is o. They differ, so no run ends in the last cell. The real answer, hello, ends in the middle of the table.

Going left to right with one list

The one-list version needs the columns to run from right to left. Change range(m, 0, -1) to range(1, m + 1) and the program gives a wrong answer:

length = 2
text = el

The text el is a real common substring, but it is not the longest one. The correct answer has length 5. When the columns run upwards, dp[j - 1] was already overwritten with a value from the current row, so one run keeps growing inside the same row.

Building the table with * on a list of lists

The table in the first example is built with a comprehension, which makes a new row each time. Writing [[0] * (m + 1)] * (n + 1) looks shorter, but it puts the same row object in every slot. The program below shows the effect on a small table.

Its output is:

[[0, 5, 0], [0, 5, 0]]

Changing one row changed both, because grid[0] and grid[1] are the same list. Build the rows with [[0] * 3 for _ in range(2)], so each row is its own list.

Off-by-one indexes

The letter at index i - 1 belongs to the row i. If you write a[i] instead, the index can reach the length of the string, which is past the last valid index. Here is a program with that mistake, run on the same strings:

a = "hellomoon"
b = "moonhello"
n = len(a)
m = len(b)
 
dp = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
    for j in range(1, m + 1):
        if a[i] == b[j]:
            dp[i][j] = dp[i - 1][j - 1] + 1
print("done")

Python stops it with this error:

Traceback (most recent call last):
  File "main.py", line 9, in <module>
    if a[i] == b[j]:
               ~^^^
IndexError: string index out of range

The message does not give the index or the length, so read the line that the caret points at. The first failure comes in row 1, when j reaches 9 and b[9] is past the end of the 9-letter string moonhello, whose valid indexes are 0 to 8. The fix is a[i - 1] and b[j - 1].

Negative indexes do not raise an error

Python counts from the end when an index is negative, so a[-1] is the last letter. If i - 1 becomes -1 by mistake, the program does not stop. It reads the wrong letter silently.

Its output is:

'n'
n

The lesson's loops start at i = 1, so i - 1 is never negative. If you change a loop to start at 0, check every - 1 in the code.

Practice

Exercise 1. Fill the table by hand for abc and bcd. Which cells are not 0, and what is the answer?

Show the answer

Only two cells are not 0. Row 2 is b from abc, and column 1 is b from bcd. They match, and the diagonal cell is 0, so the cell is 1. Row 3 is c and column 2 is c. They match, and the diagonal cell holds 1, so the cell is 2. The answer is 2, and the text is bc.

Exercise 2. What are the length and the text for banana and anana?

Show the answer

The answer is 5, and the text is anana. The whole second string appears inside the first one, starting at index 1 of banana.

Exercise 3. Run the rolling version on abc and xyz. What does it print?

Show the answer

It prints length = 0 and then text = with nothing after it. No letter is shared, so every cell is 0. The slice a[0:0] is the empty string.

Exercise 4. Change the rolling version so that it also prints the index where the best run starts in the first string.

Show the answer

The start index is best_end - best. Add the line print(f"start = {best_end - best}") before the length line. For hellomoon the output begins with start = 0, then length = 5 and text = hello.

Exercise 5. Two strings each have 2,000 letters. Estimate the memory for the full table and for the two rows. Assume each number takes 4 bytes.

Show the answer

The full table has 2,001 by 2,001 cells, which is 4,004,001 cells. At 4 bytes each, that is about 16 MB. Two rows hold 2 times 2,001 values, which is 4,002 values and about 16 KB. A Python list stores a pointer for each slot, not the number itself. On the lesson machine, sys.getsizeof([0] * 2001) returns 16064 bytes, so the Python table takes about 32 MB and the two rows take about 32 KB.

Summary

• A substring is one unbroken block of letters, so a mismatch resets the run to 0.
• dp[i][j] is the length of the run that ends at letter i - 1 of the first string and letter j - 1 of the second.
• The answer is the largest value anywhere in the table, not the last cell.
• Each row reads only the row above, so two lists are enough, and the second list must be cleared on every mismatch.
• With one list, count the columns from right to left so the old value is still there when it is read.
• Build a table of lists with a comprehension, so the rows do not share one list.