Longest Common Substring

Q: What is the time complexity of longest common substring?

The dynamic programming solution takes O(n × m) time, and O(m) memory with a single row. Extending from every pair of starts is O(n × m × min(n, m)) in the worst case. A suffix automaton reaches about O(n + m) , at the cost of a much longer program.

Q: How do you return the longest common substring itself?

Whenever a cell beats best , also record the position i in s1 where that block ends. At the end, the substring is the best letters of s1 that end there. A strict greater-than comparison keeps the first longest block found in s1 .

MediumDynamic programming

+10

You get two strings, s1 and s2. A substring is an unbroken run of letters taken from a string, such as ork from clockwork. Find the longest substring that s1 and s2 have in common and return its length. When no letter occurs in both strings, the answer is 0.

Function

longestCommonSubstring(s1: string, s2: string) → integer

s1string: the first string
s2string: the second string
Returnsinteger: the length of the longest block of letters found in both strings

Constraints

1 ≤ s1.length ≤ 1000
1 ≤ s2.length ≤ 1000
s1 and s2 consist of lowercase English letters.

Examples

Input: s1 = "clockwork"s2 = "workshop"
Output: 4
Explanation: work closes clockwork and opens workshop, so it is a common substring of length 4, and no longer block appears in both.

Input: s1 = "hammer"s2 = "harmed"
Output: 2
Explanation: ha and me occur in both words, but no run of three letters does. Both words hold h, a, m, e in that order, but harmed has an r between the a and the m.

Follow-up

Can you test whether a common substring of a given length L exists in about O(n + m) time with a rolling hash, and then binary search on L?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

Extending a match from every pair of starts rereads the same letters. Look at where a block ends instead: the common block that ends at s1[i] and s2[j] is one letter longer than the one ending at the two letters before them, or empty if the letters differ. A table of these lengths answers in O(n × m) time.

Extend from every pair of starting positions

Correct, but does not finish on the largest tests

Intuition

Every common substring starts at some position i of s1 and some position j of s2. For every pair, walk forward while the letters agree and count the steps; the largest count is the answer.

Repetitive text makes the walks long. When both strings are 1000 copies of a, every pair walks to the end of the shorter suffix: about 3.3 × 10^8 letter comparisons. The walk from (i, j) repeats the whole walk from (i+1, j+1), one letter later.

Algorithm

Set best = 0.
For every i in s1 and every j in s2, set k = 0.
While both i+k and j+k are inside their strings and s1[i+k] == s2[j+k], add 1 to k.
Keep the largest k in best, and return it.

def longestCommonSubstring(s1, s2):
    n, m = len(s1), len(s2)
    best = 0
    for i in range(n):
        for j in range(m):
            # Walk forward while the two strings agree
            k = 0
            while i + k < n and j + k < m and s1[i + k] == s2[j + k]:
                k += 1
            if k > best:
                best = k
    return best

Table of block lengths that end at each pair

Intuition

Let run[i][j] be the length of the longest common block that ends exactly at s1[i-1] and s2[j-1]; row 0 and column 0 hold 0. Such a block must contain both letters. If they differ, no block exists and the cell is 0. If they match, the block is this pair plus the block ending one letter earlier in both strings: run[i-1][j-1] + 1. Every common substring ends somewhere, so the answer is the largest cell, wherever it sits.

For hammer and harmed, the h's give 1 and the a's extend it to 2, then the r breaks the block. The second m of hammer meets the m of harmed after a mismatch of m and r, so it starts at 1, and the e's raise it to 2. No cell reaches 3.

One comparison per cell: about a million for two strings of 1000 letters, whatever the text.

Algorithm

Allocate run with n+1 rows and m+1 columns, all 0, and set best = 0.
Loop i over 1..n and, inside it, j over 1..m, comparing s1[i-1] with s2[j-1].
On a match, set run[i][j] = run[i-1][j-1] + 1 and update best.
On a mismatch, leave the cell at 0.
Return best.

def longestCommonSubstring(s1, s2):
    n, m = len(s1), len(s2)
    # run[i][j]: length of the longest block that ends at s1[i-1] and at s2[j-1]
    run = [[0] * (m + 1) for _ in range(n + 1)]
    best = 0
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if s1[i - 1] == s2[j - 1]:
                run[i][j] = run[i - 1][j - 1] + 1
                if run[i][j] > best:
                    best = run[i][j]
            # a mismatch leaves run[i][j] at 0
    return best

One row, updated from right to left

Intuition

Each cell reads only the cell diagonally up and to the left. So one array run of m+1 numbers can hold the table if you visit j from right to left: when you write run[j], the slot run[j-1] still holds the value for the previous letter of s1, which is the diagonal cell.

A mismatch must now write 0 explicitly, because the slot still holds a number from the previous row. The time stays O(n × m), and the memory drops from about 10^6 numbers to 1001.

Algorithm

Create an array run of m+1 zeros and set best = 0.
For each letter ch of s1, visit j from m down to 1.
If ch == s2[j-1], set run[j] = run[j-1] + 1 and update best.
Otherwise set run[j] = 0.
Return best.

def longestCommonSubstring(s1, s2):
    m = len(s2)
    # run[j]: length of the common block that ends at the current letter of s1 and at s2[j-1]
    run = [0] * (m + 1)
    best = 0
    for ch in s1:
        # Right to left, so run[j-1] still holds the value from the previous letter of s1
        for j in range(m, 0, -1):
            if ch == s2[j - 1]:
                run[j] = run[j - 1] + 1
                if run[j] > best:
                    best = run[j]
            else:
                run[j] = 0
    return best

Pitfalls and edge cases

Returning the last cell. run[n][m] only covers blocks that end at both last letters. For abc and abd it is 0, while ab gives 2.
Copying the larger neighbor on a mismatch. That is the subsequence rule, and it lets a block skip letters: on hammer and harmed it reports 4 instead of 2.
Walking the single row from left to right. The diagonal value is overwritten before you read it, so a against aa gives 2.
Skipping the reset in the single row. A length from the previous letter of s1 survives and later extends a block that is not there.
Walking the brute force without a bounds check. On zzzz against zz it reads past the end of the shorter string.

Frequently asked questions3

What is the difference between longest common substring and longest common subsequence?

A substring is one unbroken run of letters; a subsequence keeps the order but may leave gaps. For hammer and harmed the longest common substring has length 2 and the longest common subsequence has length 4 (hame). In the tables, a mismatch resets the substring cell to 0 but makes the subsequence cell copy its larger neighbor.

What is the time complexity of longest common substring?

The dynamic programming solution takes O(n × m) time, and O(m) memory with a single row. Extending from every pair of starts is O(n × m × min(n, m)) in the worst case. A suffix automaton reaches about O(n + m), at the cost of a much longer program.

How do you return the longest common substring itself?

Whenever a cell beats best, also record the position i in s1 where that block ends. At the end, the substring is the best letters of s1 that end there. A strict greater-than comparison keeps the first longest block found in s1.

def longestCommonSubstring(s1, s2):
    # Write code here

Test #1

Test #2

Test #3

Arguments

s1 = "clockwork"
s2 = "workshop"

Expected Output

Longest Common Substring

Function

Constraints

Examples

Hints

Solution

Extend from every pair of starting positions

Table of block lengths that end at each pair

One row, updated from right to left

Pitfalls and edge cases

Frequently asked questions3

Similar problems