Longest common substring: find a shared run of characters

The match BABC ends before the last character of the second string. Looking only at the ends of both inputs would miss it. The algorithm must consider where a run can finish and preserve the best result after that run ends.

Why a mismatch ends the run#

A substring is a consecutive piece of a string. The illustrative inputs ABABC and BABCA share BABC; the characters sit next to each other in both.

A subsequence may skip characters instead. For the smaller pair ABC and ACB, AB is a common subsequence but not a common substring. There is no shared adjacent pair in those inputs. A program must know which of these two rules it is meant to enforce.

Let dp[i][j] count matching characters in a run ending at the first string’s position i-1 and the second string’s position j-1. If those characters match, extend the run ending one position earlier in each string. If they differ, no matching run ends there.

if a[i-1] == b[j-1]: dp[i][j] = dp[i-1][j-1] + 1
else:                 dp[i][j] = 0

That zero matters. Keeping a previous best in the same cell would allow a gap and silently answer a different question. Save the overall best separately.

Try the worked example

First string (20 characters max) Second string (20 characters max) Run example

Follow the matching diagonal#

For ABABC and BABCA, these cells form the winning run. Positions here start at 1:

Position in first string	Position in second string	Character	Run ending here
2	1	B	1
3	2	A	2
4	3	B	3
5	4	C	4

Each row of this trace extends the previous one by moving forward once in each input. The bottom-right cell of the full table compares the final C of the first string with the final A of the second. It is zero, even though the answer length is four.

The Python function below stores only two table rows. A new row begins with zeros, so unmatched character pairs already have the correct value.

def longest_common_substring(a: str, b: str) -> str:
    previous = [0] * (len(b) + 1)
    best_length = best_end = 0
    for i, char_a in enumerate(a, 1):
        current = [0] * (len(b) + 1)
        for j, char_b in enumerate(b, 1):
            if char_a == char_b:
                current[j] = previous[j - 1] + 1
                if current[j] > best_length:
                    best_length, best_end = current[j], i
        previous = current
    return a[best_end - best_length:best_end]

Recover the match without storing every cell#

Whenever a longer run appears, save its length and ending position in a. The result in this example ends at position 5 and has length 4. The Python slice a[1:5] therefore returns BABC. Unlike a subsequence, the answer needs no backwards walk through several choices: it is one uninterrupted slice.

For input lengths m and n, the nested loops do O(mn) work. The two rows require O(n) working space, plus the returned substring. Making the shorter string the column input reduces that working-space bound to O(min(m,n)). The function returns an empty string when either input is empty or no characters match.

Two rows still recover this substring because its start and length identify one slice. For a sequence with gaps, recovering the letters requires more choices. The LCS storage comparison explains full-table backtracking, memoization and Hirschberg for that different requirement.

For large inputs, suffix-based methods can offer different time and memory trade-offs; this two-row method is presented because its states and result are easy to inspect. A longest palindromic substring asks a different question again: which consecutive part of one string reads the same in both directions.

Use the mismatch rule as a final check on the implementation: a common substring must break where matching adjacency breaks, even if a long match was found earlier.

Questions people also ask

2 QUESTIONS

▸ Is the answer always in the bottom-right cell?

No. A longest matching run can end before either input ends. The algorithm must remember the largest cell anywhere in the table.

▸ Does the function return every longest match?

No. It returns one. Because it only replaces the saved result for a strictly longer run, equal-length ties keep the first maximum encountered in its row-by-row scan.