Longest common substring and rolling rows

Why this matters

Tools that compare text often ask one question: what is the longest piece of text that two files share? A program that answers it has to look at many pairs of positions, and a naive version becomes slow on long files.

Dynamic programming (DP) solves this with a table. Each cell holds the answer to a small question. Later cells reuse the answers already stored in earlier cells, so the work is done once.

This lesson covers the longest common substring problem. It also teaches a memory trick called rolling rows. The trick keeps only the part of the table that the next step needs. The earlier lessons in this module covered the basic table, grid paths and the classic longest common subsequence. Here the focus is on contiguous runs and on the memory layout.

Words you will need

• String: a sequence of characters. In C++ the type is std::string.
• Substring: a piece of a string made of characters that sit next to each other. In "banana", "nan" is a substring, because the letters are in a row.
• Subsequence: characters taken in order from a string but not necessarily next to each other. In "banana", "bnn" is a subsequence, because the letters appear in that order. It is not a substring.
• Common substring: a substring that appears in both strings.
• Index: the position of a character. C++ counts from 0, so in "abc" the letter a is at index 0.
• Table: a grid of numbers, here stored as a vector of vectors. dp[i][j] means the number in row i and column j.
• Row: one line of the table. A row is a std::vector<int> in the code.
• Rolling rows: keeping only the most recent one or two rows of a table instead of all of them.
• Brute force: trying every possible answer and keeping the best. It is correct but slow.

Substring is not subsequence

The two words sound alike, so start with a clear picture. Take the string "abcde".

• "bcd" is a substring of "abcde". The letters b, c and d sit next to each other.
• "ace" is a subsequence of "abcde". The letters a, c and e appear in order, with gaps. It is not a substring, because the letters are not next to each other.

This lesson looks for substrings only. The gap-tolerant problem is the longest common subsequence, which the earlier lesson in this module covers. The change matters for the table. For substrings, a match can only continue from the cell that just before it. If the letters break, the run starts over.

A brute force first

The simplest method checks every substring of the first string. For each one, it asks whether that substring appears in the second string. It keeps the longest one that does.

Take the strings ABABC and BABCA. The substring BABC starts at index 1 of the first string and at index 0 of the second. It has four letters. No longer substring is shared, so the answer is 4.

The brute force works, but it is slow. A string of length n has about n * n / 2 substrings. Each check against the second string takes time too. For two strings of ten thousand letters, that is far too much work.

The table method avoids the repeated checks. It answers a smaller question at each cell and reuses the answers.

The idea: one cell asks how far the match runs

Compare two strings a and b. Let n be the length of a and m be the length of b. Build a table with n + 1 rows and m + 1 columns. The extra row and column stand for empty prefixes. Row 0 and column 0 are all zeros.

Define dp[i][j] as the length of the longest common run that ends exactly at position i - 1 in a and position j - 1 in b. Those positions are the letters the cell is looking at. The shift by one lets row 0 and column 0 mean "no letters yet".

The rule for each cell is short:

• If a[i - 1] and b[j - 1] are different letters, no run can end here. Set dp[i][j] to 0.
• If they are the same letter, a run may end here. Its length is one more than the run that ended one step earlier, which is dp[i - 1][j - 1]. Set dp[i][j] to dp[i - 1][j - 1] + 1.

Read the second rule slowly. The run that ended one step earlier is the match before this letter. If that earlier pair also matched, the run grows by one. If the earlier pair did not match, the earlier value is 0, and the new run starts at length 1.

Worked example: abc and bc

Let a be abc and b be bc. Here n is 3 and m is 2. The table has 4 rows and 3 columns. The output below comes from a small program that uses the same loop as Program 1 and prints each row after it is filled. It was compiled with g++ -std=c++20 -Wall.

row 0 (empty prefix of a): 0 0 0 
row 1 (prefix "a"): 0 0 0 
row 2 (prefix "ab"): 0 1 0 
row 3 (prefix "abc"): 0 0 2 

Read row 2, which is the prefix ab. Column 1 stands for b in the second string. The letter b in ab matches the letter b in bc. The run ends there with length 1, because the cell above and to the left is 0. Column 2 stands for bc. The letter c does not match the letter b at index 1 of bc, so the cell is 0.

Now read row 3, which is the prefix abc. Column 2 stands for bc. The letter c in abc matches the letter c in bc. The cell above and to the left is dp[2][1], which is 1. So this cell is 1 + 1 = 2. The run bc has length 2, and it is shared.

The answer is the largest number in the whole table. Here that is 2.

Why the answer is the biggest cell

Every common substring has an end. Pick any shared run and look at the letters where it ends. The cell for that pair of positions counts how far the match goes back, one step at a time. So the cell equals the length of the run. Since every shared run has a cell, the largest cell is the longest shared run.

The table only stores lengths. To know which substring it is, you also need to remember where the best cell was. The program in the next section does that.

Program 1: the full table in C++

This program fills the whole table and prints the longest length. It reads two lines from the keyboard. The first line is a and the second line is b.

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
 
// dp[i][j] is the length of the longest common run that ends at a[i - 1] and b[j - 1].
int longest_common_run(const std::string& a, const std::string& b) {
    const std::size_t n = a.size();
    const std::size_t m = b.size();
    std::vector<std::vector<int>> dp(n + 1, std::vector<int>(m + 1, 0));
    int best = 0;
    for (std::size_t i = 1; i <= n; ++i) {
        for (std::size_t j = 1; j <= m; ++j) {
            if (a[i - 1] == b[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
                best = std::max(best, dp[i][j]);
            } else {
                dp[i][j] = 0;
            }
        }
    }
    return best;
}
 
int main() {
    std::string a;
    std::string b;
    std::getline(std::cin, a);
    std::getline(std::cin, b);
    std::cout << "length: " << longest_common_run(a, b) << '\n';
}

Compile it with g++ -std=c++20 -Wall -o lcs_table lcs_table.cpp. Then run it and type the input. The output for ABABC and BABCA is:

ABABC
BABCA
length: 4

The line ABABC and the line BABCA are the typed input. The line length: 4 is the output.

The else branch sets the cell to 0 on purpose. It is not optional. The next section shows what goes wrong without it.

The table has (n + 1) * (m + 1) integers. For two strings of 10,000 letters, that is about 100 million integers. With 4 bytes for each integer, the table takes about 400 MB. Most of that memory is never needed again after the program has moved past a row.

Rolling rows: keep only the previous row

Look at the rule for a cell again. It uses only three neighbours: the cell above, the cell to the left and the cell above-left. Row i uses row i - 1 and nothing older. So once row i is done, rows before i - 1 are no longer needed.

This means two rows are enough. Keep one vector named prev for row i - 1 and one named cur for row i. Fill cur from prev. When the row is done, swap the two vectors. The old cur becomes the new prev, and its values are overwritten as the next row is filled.

For the same two strings of 10,000 letters, two rows of 10,001 integers take about 80 KB. The table needed about 400 MB. The answers are the same, because the rule for each cell did not change. Only the storage did.

The rolling version does not clear cur before filling it. This is safe because the loop writes every column from 1 to m in each row. Column 0 is never written. It stays 0 from the start, which is correct, because column 0 means an empty prefix of b, and no run can end there.

Program 2: rolling rows with the matching text

This version also records where the best run ends in a. Then it cuts the matching text out of a with substr. It returns both the length and the text.

#include <algorithm>
#include <iostream>
#include <string>
#include <string_view>
#include <utility>
#include <vector>
 
struct Match {
    int length;
    std::string text;
};
 
Match longest_common_substring(std::string_view a, std::string_view b) {
    const std::size_t m = b.size();
    std::vector<int> prev(m + 1, 0);  // row i - 1
    std::vector<int> cur(m + 1, 0);   // row i
    int best_len = 0;
    std::size_t best_end = 0;         // the match ends just before a[best_end]
 
    for (std::size_t i = 1; i <= a.size(); ++i) {
        for (std::size_t j = 1; j <= m; ++j) {
            if (a[i - 1] == b[j - 1]) {
                cur[j] = prev[j - 1] + 1;
                if (cur[j] > best_len) {
                    best_len = cur[j];
                    best_end = i;
                }
            } else {
                cur[j] = 0;
            }
        }
        std::swap(prev, cur);
    }
    return {best_len, std::string(a.substr(best_end - best_len, best_len))};
}
 
int main() {
    std::string a;
    std::string b;
    std::getline(std::cin, a);
    std::getline(std::cin, b);
    const Match result = longest_common_substring(a, b);
    std::cout << "length: " << result.length << '\n';
    std::cout << "text: \"" << result.text << "\"\n";
}

The variable best_end is the index just after the last letter of the best run. The loop variable i counts letters of a as 1, 2, 3, and so on. When a run of length best_len ends at i, its first letter is at index i - best_len in a. So a.substr(best_end - best_len, best_len) returns exactly that run.

Here is the output for three inputs. The first is the example from earlier. The second is programming and gaming. The third has no shared letter.

ABABC
BABCA
length: 4
text: "BABC"
 
programming
gaming
length: 4
text: "ming"
 
abc
xyz
length: 0
text: ""

In the second example, gram is not a substring of gaming, so the answer is ming. The run ming ends the word programming and the word gaming. The length-5 pieces of gaming are gamin and aming. Neither appears in programming, so no run of length 5 is shared.

In the third example, no letter is shared. The answer is length 0 and the text is empty. A program that assumes at least one letter is shared would fail here, so the empty case has to work.

Checking the program

A correct answer on three examples is not proof. A good habit is to test the table against a brute force check on many random inputs. A checker that compared the rolling version with the brute force on 3,000 random pairs of short strings over the letters a, b and c printed:

trials: 3000, failures: 0

The checker also confirmed that the returned text is really a substring of both inputs and has the reported length. Random tests like this catch off-by-one errors that a few hand-picked examples miss.

Ties: which run is printed

Sometimes two shared runs have the same length. Take abxy and xyab. Both ab and xy are shared, and each has length 2.

The program in Program 2 uses > in the comparison. So it keeps the first run it finds with the largest length. Scanning a from left to right, ab is found first. The output is ab.

Running the same input through a copy of the program that uses >= instead gives xy, which is the last run of that length. Both answers are valid. A program that is asked for one specific answer must state which one it chooses.

Common mistakes

Forgetting the else branch. Without the line that sets cur[j] to 0 when the letters differ, the cell keeps a value from two rows back. The run then appears to continue across a gap. The buggy version was tested on the input abba and aa:

abba
aa
buggy length: 2

The correct answer is 1, because aa is not a substring of abba. The buggy program claims 2. The fix is the else branch shown in Program 2.

Comparing an int to a size() value. The size of a string is an unsigned number. Comparing it with a signed int triggers a warning. A loop like this compiles with a warning under -Wall:

for (int j = 1; j <= b.size(); ++j) {

The real compiler message is:

signwarn.cpp:6:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]

The fix is to use std::size_t for the loop index, as the programs above do.

Reading the substring from the wrong end. If you store the index where a run starts, not where it ends, the substr call must use that start index. Mixing the two gives a substring of the wrong length or the wrong place. Pick one meaning for the stored index and write it in a comment.

Swapping rows and forgetting the start of each row. When the table is rolled, cur[0] must stay 0. If your code writes to column 0, the next row will start from a value that is not an empty prefix, and the lengths will be too large.

Practice

Exercise 1. Find the longest common substring of abcd and bcda by hand, then check with the program. What is the answer?

Show the answer

The answer is bcd, with length 3. The run bcd appears at index 1 of abcd and at index 0 of bcda. The program prints length: 3 and text: "bcd".

Exercise 2. Fill in the rows of the table for a equal to ab and b equal to ba. Use the rule for each cell. Write row 1 and row 2 as lists of numbers that include column 0.

Show the answer

Row 1 is 0 0 1. The letter a at index 0 of a matches the letter a at index 1 of b, so column 2 is 0 + 1 = 1.

Row 2 is 0 1 0. The letter b at index 1 of a matches the letter b at index 0 of b, so column 1 is 1. Column 2 is 0 because a and b differ.

Exercise 3. Two strings are 5,000 letters each. Compute the memory of the full table and of the two rolling rows, using 4 bytes per int.

Show the answer

The full table has 5,001 times 5,001 cells, which is 25,010,001 cells. Times 4 bytes, that is 100,040,004 bytes, about 100 MB.

The two rolling rows have 2 times 5,001 cells, which is 10,002 cells. Times 4 bytes, that is 40,008 bytes, about 40 KB.

Exercise 4. Change Program 2 so that, on a tie, it prints the run that ends later in a. Test it on abxy and xyab. What is the output?

Show the answer

Change the comparison in the inner loop from cur[j] > best_len to cur[j] >= best_len. The program then keeps the last run of the largest length. On abxy and xyab it prints text: "xy".

Exercise 5. Explain in your own words why column 0 never needs to be written in the rolling version.

Show the answer

Column 0 stands for an empty prefix of b. No letter of b is at position minus one, so no match can end in column 0. Its value stays at 0 from the first row to the last. Both prev and cur start with 0 in column 0, and the loop never writes there.

Summary

• A substring is a run of letters that sit next to each other. A subsequence can skip letters.
• The table cell dp[i][j] holds the length of the shared run that ends at a[i - 1] and b[j - 1]. It is 0 if the letters differ and one more than the cell up-left if they match.
• The answer is the largest value in the table. Keeping the position of that value gives the matching text.
• Each row depends only on the row before it, so two rolling vectors replace the full table and cut the memory from about 400 MB to about 80 KB for 10,000-letter strings.
• The else branch that sets a cell to 0 is required. Without it, a run continues across a gap, and the answer is too large.