Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

Practice › Dynamic Programming

Longest Common Substring

Medium · Dynamic Programming · Asked at Amazon, Microsoft, Flipkart

Print the length of the longest string that appears as a contiguous substring of both a and b.

Input

First line: a. Second line: b. Lowercase letters.

Output

The length.

Constraints

dp[i][j] = length of the common substring ending at a[i−1] and b[j−1]: dp[i−1][j−1] + 1 if the characters match, else 0. The answer is the maximum entry.

Example 1

Input

abcdxyz
xyzabcd

Output

4

Example 2

Input

abc
def

Output

0

Hints

  1. Unlike a subsequence, a substring must be contiguous — a mismatch resets the length to 0.
  2. dp[i][j] = length of the common substring ending exactly at a[i−1] and b[j−1]: dp[i−1][j−1] + 1 on a match, 0 otherwise.

Approach

Fill the table row by row keeping only the previous row. Each match extends the diagonal run by one; any mismatch breaks it. The answer is the largest value seen anywhere in the table, not the last cell.

Complexity: O(|a| · |b|) time · O(|b|) space

Solution

C++ solution

#include <bits/stdc++.h>
using namespace std;

int main() {
    string a, b;
    cin >> a >> b;
    int n = a.size(), m = b.size(), best = 0;
    vector<int> prev(m + 1, 0), cur(m + 1, 0);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cur[j] = a[i - 1] == b[j - 1] ? prev[j - 1] + 1 : 0;
            best = max(best, cur[j]);
        }
        swap(prev, cur);
    }
    cout << best << "\n";
    return 0;
}

Python solution

import sys

a, b = sys.stdin.read().split()[:2]
m = len(b)
prev, best = [0] * (m + 1), 0
for ca in a:
    cur = [0] * (m + 1)
    for j in range(1, m + 1):
        if ca == b[j - 1]:
            cur[j] = prev[j - 1] + 1
            if cur[j] > best:
                best = cur[j]
    prev = cur
print(best)

Java solution

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String a = sc.next(), b = sc.next();
        int n = a.length(), m = b.length(), best = 0;
        int[] prev = new int[m + 1], cur = new int[m + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                cur[j] = a.charAt(i - 1) == b.charAt(j - 1) ? prev[j - 1] + 1 : 0;
                best = Math.max(best, cur[j]);
            }
            int[] t = prev; prev = cur; cur = t;
        }
        System.out.println(best);
    }
}

Solve Longest Common Substring online · All practice problems