Longest Common Substring | DP-29

0 0 13 minutes read

Given two strings ‘X’ and ‘Y’, find the length of the longest common substring.

Examples :

Input : X = “zambiatek”, y = “GeeksQuiz”
Output : 5
Explanation:
The longest common substring is “Geeks” and is of length 5.

Input : X = “abcdxyz”, y = “xyzabcd”
Output : 4
Explanation:
The longest common substring is “abcd” and is of length 4.

Input : X = “zxabcdezy”, y = “yzabcdezx”
Output : 6
Explanation:
The longest common substring is “abcdez” and is of length 6.

Approach:
Let m and n be the lengths of the first and second strings respectively.

A simple solution is to one by one consider all substrings of the first string and for every substring check if it is a substring in the second string. Keep track of the maximum length substring. There will be O(m^2) substrings and we can find whether a string is substring on another string in O(n) time (See this). So overall time complexity of this method would be O(n * m²)

Dynamic Programming can be used to find the longest common substring in O(m*n) time. The idea is to find the length of the longest common suffix for all substrings of both strings and store these lengths in a table.

The longest common suffix has following optimal substructure property.

If last characters match, then we reduce both lengths by 1

LCSuff(X, Y, m, n) = LCSuff(X, Y, m-1, n-1) + 1 if X[m-1] = Y[n-1]

If last characters do not match, then result is 0, i.e.,

LCSuff(X, Y, m, n) = 0 if (X[m-1] != Y[n-1])

Now we consider suffixes of different substrings ending at different indexes.
The maximum length Longest Common Suffix is the longest common substring.
LCSubStr(X, Y, m, n) = Max(LCSuff(X, Y, i, j)) where 1 <= i <= m and 1 <= j <= n

Following is the iterative implementation of the above solution.

C++

/* Dynamic Programming solution to 
   find length of the
   longest common substring */
#include <iostream>
#include <string.h>
using namespace std;
 
/* Returns length of longest 
   common substring of X[0..m-1]
   and Y[0..n-1] */
int LCSubStr(char* X, char* Y, int m, int n)
{
    // Create a table to store 
    // lengths of longest
    // common suffixes of substrings.   
    // Note that LCSuff[i][j] contains 
    // length of longest common suffix 
    // of X[0..i-1] and Y[0..j-1].
 
    int LCSuff[m + 1][n + 1];
    int result = 0; // To store length of the
                    // longest common substring
 
    /* Following steps build LCSuff[m+1][n+1] in
        bottom up fashion. */
    for (int i = 0; i <= m; i++) 
    {
        for (int j = 0; j <= n; j++) 
        {
            // The first row and first column
            // entries have no logical meaning,
            // they are used only for simplicity
            // of program
            if (i == 0 || j == 0)
                LCSuff[i][j] = 0;
 
            else if (X[i - 1] == Y[j - 1]) {
                LCSuff[i][j] = LCSuff[i - 1][j - 1] + 1;
                result = max(result, LCSuff[i][j]);
            }
            else
                LCSuff[i][j] = 0;
        }
    }
    return result;
}
 
// Driver code
int main()
{
    char X[] = "OldSite:zambiatek.org";
    char Y[] = "NewSite:GeeksQuiz.com";
 
    int m = strlen(X);
    int n = strlen(Y);
 
    cout << "Length of Longest Common Substring is "
         << LCSubStr(X, Y, m, n);
    return 0;
}

Java

//  Java implementation of
// finding length of longest
// Common substring using
// Dynamic Programming
import java.io.*;
 
class GFG {
    /*
       Returns length of longest common substring
       of X[0..m-1] and Y[0..n-1]
    */
    static int LCSubStr(char X[], char Y[], int m, int n)
    {
        // Create a table to store
        // lengths of longest common
        // suffixes of substrings.
        // Note that LCSuff[i][j]
        // contains length of longest
        // common suffix of
        // X[0..i-1] and Y[0..j-1].
        // The first row and first
        // column entries have no
        // logical meaning, they are
        // used only for simplicity of program
        int LCStuff[][] = new int[m + 1][n + 1];
 
        // To store length of the longest
        // common substring
        int result = 0;
 
        // Following steps build
        // LCSuff[m+1][n+1] in bottom up fashion
        for (int i = 0; i <= m; i++) {
            for (int j = 0; j <= n; j++) {
                if (i == 0 || j == 0)
                    LCStuff[i][j] = 0;
                else if (X[i - 1] == Y[j - 1]) {
                    LCStuff[i][j]
                        = LCStuff[i - 1][j - 1] + 1;
                    result = Integer.max(result,
                                         LCStuff[i][j]);
                }
                else
                    LCStuff[i][j] = 0;
            }
        }
        return result;
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        String X = "OldSite:zambiatek.org";
        String Y = "NewSite:GeeksQuiz.com";
 
        int m = X.length();
        int n = Y.length();
 
        System.out.println(
            "Length of Longest Common Substring is "
            + LCSubStr(X.toCharArray(), Y.toCharArray(), m,
                       n));
    }
}
 
// This code is contributed by Sumit Ghosh

Python3

# Python3 implementation of Finding
# Length of Longest Common Substring
 
# Returns length of longest common
# substring of X[0..m-1] and Y[0..n-1]
 
 
def LCSubStr(X, Y, m, n):
 
    # Create a table to store lengths of
    # longest common suffixes of substrings.
    # Note that LCSuff[i][j] contains the
    # length of longest common suffix of
    # X[0...i-1] and Y[0...j-1]. The first
    # row and first column entries have no
    # logical meaning, they are used only
    # for simplicity of the program.
 
    # LCSuff is the table with zero
    # value initially in each cell
    LCSuff = [[0 for k in range(n+1)] for l in range(m+1)]
 
    # To store the length of
    # longest common substring
    result = 0
 
    # Following steps to build
    # LCSuff[m+1][n+1] in bottom up fashion
    for i in range(m + 1):
        for j in range(n + 1):
            if (i == 0 or j == 0):
                LCSuff[i][j] = 0
            elif (X[i-1] == Y[j-1]):
                LCSuff[i][j] = LCSuff[i-1][j-1] + 1
                result = max(result, LCSuff[i][j])
            else:
                LCSuff[i][j] = 0
    return result
 
 
# Driver Code
X = 'OldSite:zambiatek.org'
Y = 'NewSite:GeeksQuiz.com'
 
m = len(X)
n = len(Y)
 
print('Length of Longest Common Substring is',
      LCSubStr(X, Y, m, n))
 
# This code is contributed by Soumen Ghosh

C#

// C# implementation of finding length of longest
// Common substring using Dynamic Programming
using System;
 
class GFG {
 
    // Returns length of longest common
    // substring of X[0..m-1] and Y[0..n-1]
    static int LCSubStr(string X, string Y, int m, int n)
    {
 
        // Create a table to store lengths of
        // longest common suffixes of substrings.
        // Note that LCSuff[i][j] contains length
        // of longest common suffix of X[0..i-1]
        // and Y[0..j-1]. The first row and first
        // column entries have no logical meaning,
        // they are used only for simplicity of
        // program
        int[, ] LCStuff = new int[m + 1, n + 1];
 
        // To store length of the longest common
        // substring
        int result = 0;
 
        // Following steps build LCSuff[m+1][n+1]
        // in bottom up fashion
        for (int i = 0; i <= m; i++)
        {
            for (int j = 0; j <= n; j++)
            {
                if (i == 0 || j == 0)
                    LCStuff[i, j] = 0;
                else if (X[i - 1] == Y[j - 1]) 
                {
                    LCStuff[i, j]
                        = LCStuff[i - 1, j - 1] + 1;
 
                    result
                        = Math.Max(result, LCStuff[i, j]);
                }
                else
                    LCStuff[i, j] = 0;
            }
        }
 
        return result;
    }
 
    // Driver Code
    public static void Main()
    {
        String X = "OldSite:zambiatek.org";
        String Y = "NewSite:GeeksQuiz.com";
 
        int m = X.Length;
        int n = Y.Length;
 
        Console.Write("Length of Longest Common"
                      + " Substring is "
                      + LCSubStr(X, Y, m, n));
    }
}
 
// This code is contributed by Sam007.

PHP

<?php 
// Dynamic Programming solution to find 
// length of the longest common substring 
 
// Returns length of longest common 
// substring of X[0..m-1] and Y[0..n-1] 
function LCSubStr($X, $Y, $m, $n)
{
    // Create a table to store lengths of 
    // longest common suffixes of substrings. 
    // Notethat LCSuff[i][j] contains length 
    // of longest common suffix of X[0..i-1] 
    // and Y[0..j-1]. The first row and
    // first column entries have no logical 
    // meaning, they are used only for 
    // simplicity of program
    $LCSuff = array_fill(0, $m + 1,
              array_fill(0, $n + 1, NULL));
    $result = 0; // To store length of the 
                 // longest common substring
 
    // Following steps build LCSuff[m+1][n+1] 
    // in bottom up fashion. 
    for ($i = 0; $i <= $m; $i++)
    {
        for ($j = 0; $j <= $n; $j++)
        {
            if ($i == 0 || $j == 0)
                $LCSuff[$i][$j] = 0;
 
            else if ($X[$i - 1] == $Y[$j - 1])
            {
                $LCSuff[$i][$j] = $LCSuff[$i - 1][$j - 1] + 1;
                $result = max($result, 
                              $LCSuff[$i][$j]);
            }
            else $LCSuff[$i][$j] = 0;
        }
    }
    return $result;
}
 
// Driver Code 
$X = "OldSite:zambiatek.org";
$Y = "NewSite:GeeksQuiz.com";
 
$m = strlen($X);
$n = strlen($Y);
 
echo "Length of Longest Common Substring is " . 
                      LCSubStr($X, $Y, $m, $n);
                       
// This code is contributed by ita_c
?>

Javascript

<script>
 
// JavaScript implementation of
// finding length of longest
// Common substring using 
// Dynamic Programming
 
    /*
     Returns length of longest common 
     substring of X[0..m-1] and Y[0..n-1]
     */
    function LCSubStr( X,  Y , m , n) {
        // Create a table to store
        // lengths of longest common
        // suffixes of substrings.
        // Note that LCSuff[i][j]
        // contains length of longest
        // common suffix of
        // X[0..i-1] and Y[0..j-1].
        // The first row and first
        // column entries have no
        // logical meaning, they are
        // used only for simplicity of program
         
        var LCStuff = 
        Array(m + 1).fill().map(()=>Array(n + 1).fill(0));
 
        // To store length of the longest
        // common substring
        var result = 0;
 
        // Following steps build
        // LCSuff[m+1][n+1] in bottom up fashion
        for (i = 0; i <= m; i++) {
            for (j = 0; j <= n; j++) {
                if (i == 0 || j == 0)
                    LCStuff[i][j] = 0;
                else if (X[i - 1] == Y[j - 1]) {
                    LCStuff[i][j] = LCStuff[i - 1][j - 1] + 1;
                    result = Math.max(result, LCStuff[i][j]);
                } else
                    LCStuff[i][j] = 0;
            }
        }
        return result;
    }
 
    // Driver Code
     
        var X = "OldSite:zambiatek.org";
        var Y = "NewSite:GeeksQuiz.com";
 
        var m = X.length;
        var n = Y.length;
 
        document.write("Length of Longest Common Substring is " +
        LCSubStr(X, Y, m, n));
 
// This code contributed by Rajput-Ji
 
</script>

Output

Length of Longest Common Substring is 10

Time Complexity: O(m*n)
Auxiliary Space: O(m*n), since m*n extra space has been taken.

Another Approach: (Space optimized approach).
In the above approach, we are only using the last row of the 2-D array only, hence we can optimize the space by using
a 2-D array of dimension 2*(min(n,m)).

Below is the implementation of the above approach:

C++

// C++ implementation of the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the length of the
// longest LCS
int LCSubStr(string s, string t, int n, int m)
{
   
    // Create DP table
    int dp[2][m + 1];
    int res = 0;
       
      dp[0][0] = 0;
      dp[1][0] = 0;
 
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (s[i - 1] == t[j - 1]) {
                dp[i % 2][j] = dp[(i - 1) % 2][j - 1] + 1;
                if (dp[i % 2][j] > res)
                    res = dp[i % 2][j];
            }
            else
                dp[i % 2][j] = 0;
        }
    }
    return res;
}
 
// Driver Code
int main()
{
    string X = "OldSite:zambiatek.org";
    string Y = "NewSite:GeeksQuiz.com";
 
    int m = X.length();
    int n = Y.length();
 
    cout << LCSubStr(X, Y, m, n);
    return 0;
    cout << "GFG!";
    return 0;
}
 
// This code is contributed by rajsanghavi9.

Java

// Java implementation of the above approach
import java.io.*;
class GFG
{
   
    // Function to find the length of the
    // longest LCS
    static int LCSubStr(String s,String t,
                        int n,int m) 
    {  
       
        // Create DP table
        int dp[][]=new int[2][m+1];
        int res=0;
      
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                if(s.charAt(i-1)==t.charAt(j-1))
                {
                    dp[i%2][j]=dp[(i-1)%2][j-1]+1;
                    if(dp[i%2][j]>res)
                        res=dp[i%2][j];
                }
                else dp[i%2][j]=0;
            }
        }
        return res;
    }
   
    // Driver Code
    public static void main (String[] args)
    {
        String X="OldSite:zambiatek.org"; 
        String Y="NewSite:GeeksQuiz.com";
         
        int m=X.length();
        int n=Y.length();
         
        // Function call
        System.out.println(LCSubStr(X,Y,m,n));
         
    }
}

Python3

# Python implementation of the above approach
 
# Function to find the length of the
# longest LCS
def LCSubStr(s, t, n, m):
   
    # Create DP table
    dp = [[0 for i in range(m + 1)] for j in range(2)]
    res = 0
     
    for i in range(1,n + 1):
        for j in range(1,m + 1):
            if(s[i - 1] == t[j - 1]):
                dp[i % 2][j] = dp[(i - 1) % 2][j - 1] + 1
                if(dp[i % 2][j] > res):
                    res = dp[i % 2][j]
            else:
                dp[i % 2][j] = 0
    return res
 
# Driver Code
X = "OldSite:zambiatek.org"
Y = "NewSite:GeeksQuiz.com"
m = len(X)
n = len(Y)
 
# Function call
print(LCSubStr(X,Y,m,n))
 
# This code is contributed by avanitrachhadiya2155

C#

// C# implementation of the above approach
using System;
public class GFG
{
 
  // Function to find the length of the
  // longest LCS
  static int LCSubStr(string s,string t,
                      int n,int m) 
  {  
 
    // Create DP table
    int[,] dp = new int[2, m + 1];
    int res = 0;
 
    for(int i = 1; i <= n; i++)
    {
      for(int j = 1; j <= m; j++)
      {
        if(s[i - 1] == t[j - 1])
        {
          dp[i % 2, j] = dp[(i - 1) % 2, j - 1] + 1;
          if(dp[i % 2, j] > res)
            res = dp[i % 2, j];
        }
        else dp[i % 2, j] = 0;
      }
    }
    return res;
  }
 
  // Driver Code
  static public void Main (){
    string X = "OldSite:zambiatek.org"; 
    string Y = "NewSite:GeeksQuiz.com";
 
    int m = X.Length;
    int n = Y.Length;
 
    // Function call
    Console.WriteLine(LCSubStr(X,Y,m,n));
  }
}
 
// This code is contributed by rag2127

Javascript

<script>
// JavaScript implementation of the above approach
 
    // Function to find the length of the
    // longest LCS
    function LCSubStr(s, t, n, m) 
    {  
       
        // Create DP table
        var dp = Array(2).fill().map(()=>Array(m+ 1).fill(0));
        var res = 0;
      
        for(var i = 1; i <= n; i++)
        {
            for(var j = 1; j <= m; j++)
            {
                if(s.charAt(i - 1) == t.charAt(j - 1))
                {
                    dp[i % 2][j] = dp[(i - 1) % 2][j - 1] + 1;
                    if(dp[i % 2][j] > res)
                        res = dp[i % 2][j];
                }
                else dp[i % 2][j] = 0;
            }
        }
        return res;
    }
   
    // Driver Code
        var X = "OldSite:zambiatek.org"; 
        var Y = "NewSite:GeeksQuiz.com";
         
        var m = X.length;
        var n = Y.length;
         
        // Function call
        document.write(LCSubStr(X, Y, m, n));
 
// This code is contributed by shivanisinghss2110
</script>

Output

Time Complexity: O(n*m)
Auxiliary Space: O(min(m,n))

Another Approach: (Using recursion)
Here is the recursive solution of the above approach.

C++

// C++ program using to find length of the
// longest common substring  recursion
#include <iostream>
 
using namespace std;
 
string X, Y;
 
// Returns length of function f
// or longest common substring 
// of X[0..m-1] and Y[0..n-1]
int lcs(int i, int j, int count)
{
 
    if (i == 0 || j == 0)
        return count;
 
    if (X[i - 1] == Y[j - 1]) {
        count = lcs(i - 1, j - 1, count + 1);
    }
    count = max(count,
                max(lcs(i, j - 1, 0),
                    lcs(i - 1, j, 0)));
    return count;
}
 
// Driver code
int main()
{
    int n, m;
 
    X = "abcdxyz";
    Y = "xyzabcd";
 
    n = X.size();
    m = Y.size();
 
    cout << lcs(n, m, 0);
 
    return 0;
}

Java

// Java program using to find length of the
// longest common substring recursion
import java.io.*;
class GFG {
 
    static String X, Y;
    // Returns length of function 
    // for longest common
    // substring of X[0..m-1] and Y[0..n-1]
    static int lcs(int i, int j, int count)
    {
 
        if (i == 0 || j == 0) 
        {
            return count;
        }
 
        if (X.charAt(i - 1) 
            == Y.charAt(j - 1)) 
        {
            count = lcs(i - 1, j - 1, count + 1);
        }
        count = Math.max(count, 
                         Math.max(lcs(i, j - 1, 0),
                                  lcs(i - 1, j, 0)));
        return count;
    }
     
    // Driver code
    public static void main(String[] args)
    {
        int n, m;
        X = "abcdxyz";
        Y = "xyzabcd";
 
        n = X.length();
        m = Y.length();
 
        System.out.println(lcs(n, m, 0));
    }
}
// This code is contributed by Rajput-JI

Python3

# Python3 program using to find length of
# the longest common substring recursion
 
# Returns length of function for longest
# common substring of X[0..m-1] and Y[0..n-1]
 
 
def lcs(i, j, count):
 
    if (i == 0 or j == 0):
        return count
 
    if (X[i - 1] == Y[j - 1]):
        count = lcs(i - 1, j - 1, count + 1)
 
    count = max(count, max(lcs(i, j - 1, 0),
                           lcs(i - 1, j, 0)))
 
    return count
 
 
# Driver code
if __name__ == "__main__":
 
    X = "abcdxyz"
    Y = "xyzabcd"
 
    n = len(X)
    m = len(Y)
 
    print(lcs(n, m, 0))
 
# This code is contributed by Ryuga

C#

// C# program using to find length
// of the longest common substring
// recursion
using System;
 
class GFG {
    static String X, Y;
 
    // Returns length of function for
    // longest common substring of
    // X[0..m-1] and Y[0..n-1]
    static int lcs(int i, int j, int count)
    {
 
        if (i == 0 || j == 0) {
            return count;
        }
 
        if (X[i - 1] == Y[j - 1]) {
            count = lcs(i - 1, j - 1, count + 1);
        }
        count = Math.Max(count, Math.Max(lcs(i, j - 1, 0),
                                         lcs(i - 1, j, 0)));
        return count;
    }
 
    // Driver code
    public static void Main()
    {
        int n, m;
        X = "abcdxyz";
        Y = "xyzabcd";
 
        n = X.Length;
        m = Y.Length;
 
        Console.Write(lcs(n, m, 0));
    }
}
 
// This code is contributed by Rajput-JI

PHP

<?php
// PHP program using to find length of the 
// longest common substring recursion 
 
// Returns length of function for 
// longest common substring of
// X[0..m-1] and Y[0..n-1] 
function lcs($i, $j, $count, &$X, &$Y) 
{ 
    if ($i == 0 || $j == 0) 
        return $count; 
         
    if ($X[$i - 1] == $Y[$j - 1]) 
    { 
        $count = lcs($i - 1, $j - 1, 
                     $count + 1, $X, $Y); 
    } 
        $count = max($count, lcs($i, $j - 1, 0, $X, $Y), 
                             lcs($i - 1, $j, 0, $X, $Y)); 
    return $count; 
} 
 
// Driver code 
$X = "abcdxyz"; 
$Y = "xyzabcd"; 
 
$n = strlen($X); 
$m = strlen($Y); 
 
echo lcs($n, $m, 0, $X, $Y); 
 
// This code is contributed
// by rathbhupendra
?>

Javascript

<script>
    // Javascript program using to find length of the
    // longest common substring  recursion
    let X, Y;
  
    // Returns length of function f
    // or longest common substring 
    // of X[0..m-1] and Y[0..n-1]
    function lcs(i, j, count)
    {
      
        if (i == 0 || j == 0)
            return count;
      
        if (X[i - 1] == Y[j - 1]) {
            count = lcs(i - 1, j - 1, count + 1);
        }
        count = Math.max(count,
                    Math.max(lcs(i, j - 1, 0),
                        lcs(i - 1, j, 0)));
        return count;
    }
     
    let n, m;
  
    X = "abcdxyz";
    Y = "xyzabcd";
  
    n = X.length;
    m = Y.length;
  
    document.write(lcs(n, m, 0));
     
    // This code is contributed by divyeshrabadiya07.
</script>

Output

Time complexity: O(2^max(m,n)) as the function is doing two recursive calls – lcs(i, j-1, 0) and lcs(i-1, j, 0) when characters at X[i-1] != Y[j-1]. So it will give a worst case time complexity as 2^N, where N = max(m, n), m and n is the length of X and Y string.
Auxiliary Space: O(1): as the function call is not using any extra space (function is just using a recursive call stack which we generally doesn’t consider in auxiliary space).

Maximum Space Optimization:Ad

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!