Longest common substring

Lesson · 9 min read · Dynamic programming · Longest common substring

Like the common subsequence, but the shared part must be contiguous. One change to the recurrence: a mismatch resets to zero.

Contiguous changes the recurrence

A substring (for lists, a subarray) has no gaps. For [1, 2, 3, 2, 1] and [3, 2, 1, 4, 7] the longest shared block is 3, 2, 1, length 3.

The prefix state of the subsequence problem does not work directly, because a block that has been broken cannot be continued. Use the same trick as for the increasing subsequence: fix the end. Let E(i, j) be the length of the longest common block ending exactly at a[i − 1] and b[j − 1].

Recurrence

E(i, j)

if a[i − 1] = b[j − 1]: 1 + E(i − 1, j − 1) (extend the block ending just before);
otherwise 0 (no common block ends here).

answer

the largest E(i, j) anywhere in the table.

Bottom-up

E(i, j) for [1, 2, 3, 2, 1] and [3, 2, 1, 4, 7]. Matches extend along diagonals; mismatches are 0.

Step 1 / 6

Base cases filled first.
Step 2 / 6

Row 1 filled.
Step 3 / 6

Row 2 filled.
Step 4 / 6

Row 3 filled.
Step 5 / 6

Row 2 filled.
Step 6 / 6

Row 1 filled. The largest entry is 3: the block 3, 2, 1, read along its diagonal.

Implementation

Each row reads only the previous row, so two rows are enough:

def longest_common_block(nums1, nums2):
    m = len(nums2)
    prev = [0] * (m + 1)                # E for the previous row
    best = 0
    for x in nums1:
        cur = [0] * (m + 1)
        for j in range(1, m + 1):
            if x == nums2[j - 1]:
                cur[j] = prev[j - 1] + 1     # extend the block ending one step earlier
                best = max(best, cur[j])
        prev = cur
    return best

#include <algorithm>
#include <vector>

int solve(const std::vector<int>& nums1, const std::vector<int>& nums2) {
    const int m = nums2.size();
    std::vector<int> prev(m + 1, 0), cur(m + 1, 0);
    int best = 0;
    for (int x : nums1) {
        for (int j = 1; j <= m; ++j) {
            cur[j] = x == nums2[j - 1] ? prev[j - 1] + 1 : 0;
            best = std::max(best, cur[j]);
        }
        std::swap(prev, cur);
    }
    return best;
}

class Solution {
    public int longestCommonBlock(int[] nums1, int[] nums2) {
        int m = nums2.length, best = 0;
        int[] prev = new int[m + 1], cur = new int[m + 1];
        for (int x : nums1) {
            for (int j = 1; j <= m; j++) {
                cur[j] = x == nums2[j - 1] ? prev[j - 1] + 1 : 0;
                best = Math.max(best, cur[j]);
            }
            int[] t = prev; prev = cur; cur = t;
        }
        return best;
    }
}

function longestCommonBlock(nums1, nums2) {
  const m = nums2.length;
  let prev = new Array(m + 1).fill(0), best = 0;
  for (const x of nums1) {
    const cur = new Array(m + 1).fill(0);
    for (let j = 1; j <= m; j++) if (x === nums2[j - 1]) { cur[j] = prev[j - 1] + 1; best = Math.max(best, cur[j]); }
    prev = cur;
  }
  return best;
}

fn solve(nums1: &[i64], nums2: &[i64]) -> i64 {
    let m = nums2.len();
    let mut prev = vec![0i64; m + 1];
    let mut best = 0;
    for &x in nums1 {
        let mut cur = vec![0i64; m + 1];
        for j in 1..=m {
            if x == nums2[j - 1] {
                cur[j] = prev[j - 1] + 1;
                best = best.max(cur[j]);
            }
        }
        prev = cur;
    }
    best
}

solve :: [Int] -> [Int] -> Int
solve a b = maximum (0 : concat rows)
  where
    -- each row: E for one element of the first list against every element of the second
    rows = tail (scanl row (replicate (length b) 0) a)
    row prev x = zipWith3 (\y diag _ -> if x == y then diag + 1 else 0) b (0 : prev) prev

The same code is the reference solution to Longest common block, where it is compiled and run against the tests in all six languages.

TimeO(n · m)

SpaceO(m)

The answer is not in the corner of the table, as for the subsequence: it is the maximum anywhere. That difference, "ends exactly here" against "within the first i and j", recurs throughout DP.