Tutorialspoint.dev

Longest Common Substring (Space optimized DP solution)

Given two strings ‘X’ and ‘Y’, find the length of longest common substring. Expected space complexity is linear.

Examples :

Input : X = "GeeksforGeeks", Y = "GeeksQuiz"
Output : 5
The longest common substring is "Geeks" and is of
length 5.

Input : X = "abcdxyz", Y = "xyzabcd"
Output : 4
The longest common substring is "abcd" and is of
length 4.

longest-common-substring



We have discussed Dynamic programming based solution for Longest common substring. The auxiliary space used by the solution is O(m*n), where m and n are lengths of string X and Y. The space used by solution can be reduced to O(2*n).
Suppose we are at position mat[i][j]. Now if X[i-1] == Y[j-1], then we add the value of mat[i-1][j-1] to our result. That is we add value from previous row and value for all other rows below the previous row are never used. So, at a time we are using only two consecutive rows. This observation can be used to reduce the space required to find length of longest common substring.
Instead of creating a matrix of size m*n, we create a matrix of size 2*n. A variable currRow is used to represent that either row 0 or row 1 of this matrix is currently used to find length. Initially row 0 is used as current row for the case when length of string X is zero. At the end of each iteration, current row is made previous row and previous row is made new current row.

C++

// Space optimized CPP implementation of longest
// common substring.
#include <bits/stdc++.h>
using namespace std;
  
// Function to find longest common substring.
int LCSubStr(string X, string Y)
{
    // Find length of both the strings.
    int m = X.length();
    int n = Y.length();
  
    // Variable to store length of longest
    // common substring.
    int result = 0;
  
    // Matrix to store result of two
    // consecutive rows at a time.
    int len[2][n];
  
    // Variable to represent which row of
    // matrix is current row.
    int currRow = 0;
  
    // For a particular value of i and j,
    // len[currRow][j] stores length of longest
    // common substring in string X[0..i] and Y[0..j].
    for (int i = 0; i <= m; i++) {
        for (int j = 0; j <= n; j++) {
            if (i == 0 || j == 0) {
                len[currRow][j] = 0;
            }
            else if (X[i - 1] == Y[j - 1]) {
                len[currRow][j] = len[1 - currRow][j - 1] + 1;
                result = max(result, len[currRow][j]);
            }
            else {
                len[currRow][j] = 0;
            }
        }
  
        // Make current row as previous row and previous
        // row as new current row.
        currRow = 1 - currRow;
    }
  
    return result;
}
  
int main()
{
    string X = "GeeksforGeeks";
    string Y = "GeeksQuiz";
  
    cout << LCSubStr(X, Y);
    return 0;
}

Java

// Space optimized CPP implementation of 
// longest common substring.
import java.io.*;
import java.util.*;
  
public class GFG {
      
    // Function to find longest
    // common substring.
    static int LCSubStr(String X, String Y)
    {
          
        // Find length of both the strings.
        int m = X.length();
        int n = Y.length();
      
        // Variable to store length of longest
        // common substring.
        int result = 0;
      
        // Matrix to store result of two
        // consecutive rows at a time.
        int [][]len = new int[2][n];
      
        // Variable to represent which row of
        // matrix is current row.
        int currRow = 0;
      
        // For a particular value of
        // i and j, len[currRow][j] 
        // stores length of longest
        // common substring in string
        // X[0..i] and Y[0..j].
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0 || j == 0) {
                    len[currRow][j] = 0;
                }
                else if (X.charAt(i - 1) == 
                              Y.charAt(j - 1))
                {
                    len[currRow][j] =
                      len[(1 - currRow)][(j - 1)]
                                             + 1;
                    result = Math.max(result, 
                                len[currRow][j]);
                }
                else
                {
                    len[currRow][j] = 0;
                }
            }
      
            // Make current row as previous
            // row and previous row as 
            // new current row.
            currRow = 1 - currRow;
        }
      
        return result;
    }
      
    // Driver Code
    public static void main(String args[])
    {
        String X = "GeeksforGeeks";
        String Y = "GeeksQuiz";
      
        System.out.print(LCSubStr(X, Y));
    }
}
  
// This code is contributed by 
// Manish Shaw (manishshaw1)

Python3

# Space optimized Python3 implementation  
# of longest common substring. 
import numpy as np
  
# Function to find longest common substring. 
def LCSubStr(X, Y) : 
  
    # Find length of both the strings. 
    m = len(X) 
    n = len(Y) 
  
    # Variable to store length of 
    # longest common substring. 
    result = 0
  
    # Matrix to store result of two 
    # consecutive rows at a time. 
    len_mat = np.zeros((2, n)) 
  
    # Variable to represent which row  
    # of matrix is current row. 
    currRow = 0
  
    # For a particular value of i and j, 
    # len_mat[currRow][j] stores length of 
    # longest common substring in string 
    # X[0..i] and Y[0..j]. 
    for i in range(m) : 
        for j in range(n) :
                          
            if (i == 0 | j == 0) : 
                len_mat[currRow][j] = 0
              
            elif (X[i - 1] == Y[j - 1]) :
                                  
                len_mat[currRow][j] = len_mat[1 - currRow][j - 1] + 1
                result = max(result, len_mat[currRow][j])
              
            else
                len_mat[currRow][j] = 0
              
        # Make current row as previous row and 
        # previous row as new current row. 
        currRow = 1 - currRow
  
    return result
  
# Driver Code
if __name__ == "__main__"
  
    X = "GeeksforGeeks"
    Y = "GeeksQuiz"
  
    print(LCSubStr(X, Y))
  
# This code is contributed by Ryuga

C#

// Space optimized C# implementation
// of longest common substring.
using System;
using System.Collections.Generic;
class GFG {
      
    // Function to find longest
    // common substring.
    static int LCSubStr(string X, string Y)
    {
          
        // Find length of both the strings.
        int m = X.Length;
        int n = Y.Length;
      
        // Variable to store length of longest
        // common substring.
        int result = 0;
      
        // Matrix to store result of two
        // consecutive rows at a time.
        int [,]len = new int[2,n];
      
        // Variable to represent which row of
        // matrix is current row.
        int currRow = 0;
      
        // For a particular value of
        // i and j, len[currRow][j] 
        // stores length of longest
        // common substring in string
        // X[0..i] and Y[0..j].
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0 || j == 0) {
                    len[currRow,j] = 0;
                }
                else if (X[i - 1] == Y[j - 1]) {
                    len[currRow,j] = len[(1 - currRow), 
                                          (j - 1)] + 1;
                    result = Math.Max(result, len[currRow, j]);
                }
                else 
                {
                    len[currRow,j] = 0;
                }
            }
      
            // Make current row as previous
            // row and previous row as 
            // new current row.
            currRow = 1 - currRow;
        }
      
        return result;
    }
      
      
    // Driver Code
    public static void Main()
    {
        string X = "GeeksforGeeks";
        string Y = "GeeksQuiz";
      
        Console.Write(LCSubStr(X, Y));
    }
}
  
// This code is contributed by 
// Manish Shaw (manishshaw1)

PHP

<?php
// Space optimized PHP implementation 
// of longest common substring.
  
// Function to find 
// longest common substring.
function LCSubStr($X, $Y)
{
    // Find length of
    // both the strings.
    $m = strlen($X);
    $n = strlen($Y);
  
    // Variable to store length 
    // of longest common substring.
    $result = 0;
  
    // Matrix to store result of two
    // consecutive rows at a time.
    $len = array(array(), array(), );
  
    // Variable to represent which 
    // row of matrix is current row.
    $currRow = 0;
  
    // For a particular value of 
    // i and j, len[currRow][j] 
    // stores length of longest 
    // common substring in string 
    // X[0..i] and Y[0..j].
    for ($i = 0; $i <= $m; $i++) 
    {
        for ($j = 0; $j <= $n; $j++) 
        {
            if ($i == 0 || $j == 0) 
            {
                $len[$currRow][$j] = 0;
            }
            else if ($X[$i - 1] == $Y[$j - 1]) 
            {
                $len[$currRow][$j] = 
                        $len[1 - $currRow][$j - 1] + 1;
                  
                $result = max($result
                              $len[$currRow][$j]);
            }
            else 
            {
                $len[$currRow][$j] = 0;
            }
        }
  
        // Make current row as 
        // previous row and previous
        // row as new current row.
        $currRow = 1 - $currRow;
    }
  
    return $result;
}
  
// Driver Code
$X = "GeeksforGeeks";
$Y = "GeeksQuiz";
  
print (LCSubStr($X, $Y));
  
// This code is contributed by 
// Manish Shaw(manishshaw1)
?>

Output :

5

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



This article is attributed to GeeksforGeeks.org

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter