In this article, we will learn to resolve the Longest Common Substring problem by using a dynamic programming algorithm

Problem

  • Given two strings, S of length m and T of length n

  • Write an algorithm to find the longest substring of both S and T

Example

  • Input: given two strings "ABABC" and "BABCA"

  • Expected output: "ABC"

Approach: Bottom Up Dynamic Programming

  • Optimal substructure: L(i, j) = L(i-1, j-1) + 1 if S(i-1) == T(j-1) with L(i, j) is the length of the common substring at character S(i) and T(j)

    For the above example, the longest common substring "ABC" has the length at the last common character C of both S and T, L(5, 4), equals to the length at the immediate preceding common character B, L(4, 3), plus 1

  • Bottom-up filling the 2D array L[m+1][n+1] and keep track the max length and start index of the longest common substring

public class String_LongestCommon {  
    static String longestCommonSubstring(String S, String T) {
        int m = S.length();
        int n = T.length();
        int[][] lengths = new int[m+1][n+1];
        int maxLength = 0;
        int endIndex = 0;

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0 || j== 0) {
                    lengths[i][j] = 0;
                }
                else if(S.charAt(i-1) == T.charAt(j-1)) {
                    lengths[i][j] = lengths[i-1][j-1] + 1;
                    maxLength = Math.max(maxLength, lengths[i][j]);
                    endIndex = i;
                } else {
                    lengths[i][j] = 0;
                }
            }
        }

        return S.substring(endIndex - maxLength + 1, endIndex + 1);
    }

    public static void main(String[] args) {
        System.out.println(longestCommonSubstring("ABABC", "BABCA"));
    }
}

Complexity

  • Time complexity: O(mn)

  • Space complexity: O(mn)

AlgorithmDynamic Programming