Table of contents

Longest Common Substring

Given two strings X and Y, find the length of the longest common substring. A substring is a contiguous sequence of characters within a string, and the longest common substring is the longest contiguous segment that appears in both strings.

Input/Output Examples

plaintext
Example 1:
Input: X = "abcde", Y = "abfce"
Output: 2
Explanation: The longest common substring is "ab", which has a length of 2.

Example 2:
Input: X = "abcdef", Y = "zabcf"
Output: 3
Explanation: The longest common substring is "abc", which has a length of 3.

Approach to find the Longest Common Substring

  1. Dynamic Programming Approach:
    • Create a 2D DP table, dp[i][j], where i and j are indices of the strings X and Y.
    • dp[i][j] represents the length of the longest common substring ending at X[i-1] and Y[j-1].
    • If X[i-1] == Y[j-1], then dp[i][j] = dp[i-1][j-1] + 1 (we extend the previous common substring).
    • If the characters don't match, dp[i][j] = 0 (reset the substring).
  2. Algorithm:
    • Initialize a 2D DP table of size (len(X)+1) x (len(Y)+1) filled with zeros.
    • Traverse both strings, and for each pair of characters, update the DP table according to the rules above.
    • Keep track of the maximum value in the DP table, which represents the length of the longest common substring.
  3. Edge Cases:
    • If either string is empty, the longest common substring is of length 0.
    • If there are no common substrings, return 0.

C++ Program to find the Longest Common Substring

cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// Function to find the length of the longest common substring
int longestCommonSubstring(string X, string Y) {
    int m = X.length();
    int n = Y.length();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
    int maxLength = 0;

    // Build the DP table
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (X[i - 1] == Y[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
                maxLength = max(maxLength, dp[i][j]);
            }
        }
    }

    return maxLength;
}

int main() {
    string X = "abcde";
    string Y = "abfce";
    
    int result = longestCommonSubstring(X, Y);
    cout << "Length of the longest common substring: " << result << endl;
    
    return 0;
}

Java Program to find the Longest Common Substring

java
public class LongestCommonSubstring {

    // Function to find the length of the longest common substring
    public static int longestCommonSubstring(String X, String Y) {
        int m = X.length();
        int n = Y.length();
        int[][] dp = new int[m + 1][n + 1];
        int maxLength = 0;

        // Build the DP table
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (X.charAt(i - 1) == Y.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    maxLength = Math.max(maxLength, dp[i][j]);
                }
            }
        }

        return maxLength;
    }

    public static void main(String[] args) {
        String X = "abcde";
        String Y = "abfce";
        
        int result = longestCommonSubstring(X, Y);
        System.out.println("Length of the longest common substring: " + result);
    }
}

Python Program to find the Longest Common Substring

python
# Function to find the length of the longest common substring
def longest_common_substring(X, Y):
    m, n = len(X), len(Y)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    max_length = 0

    # Build the DP table
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if X[i - 1] == Y[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
                max_length = max(max_length, dp[i][j])

    return max_length

# Example usage
if __name__ == "__main__":
    X = "abcde"
    Y = "abfce"
    result = longest_common_substring(X, Y)
    print("Length of the longest common substring:", result)

Time Complexity:

  • O(m * n): We iterate through both strings once, where m is the length of string X and n is the length of string Y.

Space Complexity:

  • O(m * n): We use a 2D DP table of size (m + 1) x (n + 1).

DSA

Related Articles