# Longest common substring using dynamic programming

This article discusses the implementation of finding the longest common substring between two strings using dynamic programming. We will explore the problem statement, provide a pseudocode algorithm with explanations, and analyze the resultant output with the time complexity of the code.

## Problem Statement

The problem is to find the longest common substring between two given strings. A substring is a contiguous sequence of characters within a string. For example, in the strings "xycmitimesnxycode" and "xycstimesce," the longest common substring is "times," which appears in both strings.

## Pseudocode Algorithm

To solve this problem efficiently, we can use dynamic programming. The following pseudocode algorithm outlines the steps involved:

```function longestCommonSubstring(str1, str2):
n = length of str1
m = length of str2

if n <= 0 or m <= 0:
return

dp = 2D array of size (n+1) x (m+1)
count = 0

for i from 0 to n:
for j from 0 to m:
if i == 0 or j == 0:
dp[i][j] = 0
else if str1[i-1] == str2[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
count = max(count, dp[i][j])
else:
dp[i][j] = 0

print "Given: " + str1 + " " + str2
print "Result: " + count
```

The algorithm uses a two-dimensional array, `dp`, to store the lengths of common substrings. The variable `count` keeps track of the maximum length encountered so far. The algorithm iterates over each character in both strings, comparing them and updating the `dp` array accordingly. Finally, it prints the given strings and the length of the longest common substring.

## Code Solution

``````/*
C program for
Longest common substring using dynamic programming
*/
#include <stdio.h>
#include <string.h>

int maxValue(int a, int b)
{
if (a > b)
{
return a;
}
return b;
}
void longestCommonSubstring(char *str1, char *str2)
{
// Get the length of given string
int n = strlen(str1);
int m = strlen(str2);
if (n <= 0 || m <= 2)
{
return;
}
int dp[n + 1][m + 1];
int count = 0;
// Execute loop through by size of str1
for (int i = 0; i <= n; ++i)
{
// Execute loop through by size of str2
for (int j = 0; j <= m; ++j)
{
if (i == 0 || j == 0)
{
// Set default value when i and j is zero
dp[i][j] = 0;
}
else if (str1[i - 1] == str2[j - 1])
{
// When str1[i-1] and str2[j - 1] are same
// Then update dp[i][j] value
dp[i][j] = dp[i - 1][j - 1] + 1;
// Get max value of given parameters
count = maxValue(count, dp[i][j]);
}
else
{
// set zero
dp[i][j] = 0;
}
}
}
// Display result
printf(" Given  : %s %s", str1, str2);
printf("\n Result : %d \n", count);
}
int main(int argc, char
const *argv[])
{
// Test
// times
longestCommonSubstring("xycmitimesnxycode", "xycstimesce");
// icd
longestCommonSubstring("abxicde", "xyzavbicdn");
return 0;
}``````

#### Output

`````` Given  : xycmitimesnxycode xycstimesce
Result : 5
Given  : abxicde xyzavbicdn
Result : 3``````
``````/*
Java program for
Longest common substring using dynamic programming
*/
public class CommonSubstring
{
public int maxValue(int a, int b)
{
if (a > b)
{
return a;
}
return b;
}
public void longestCommonSubstring(String str1, String str2)
{
// Get the length of given string
int n = str1.length();
int m = str2.length();
if (n <= 0 || m <= 2)
{
return;
}
// Use to collect common substring result
int[][] dp = new int[n + 1][m + 1];
int count = 0;
// Execute loop through by size of str1
for (int i = 0; i <= n; ++i)
{
// Execute loop through by size of str2
for (int j = 0; j <= m; ++j)
{
if (i == 0 || j == 0)
{
// Set default value when i and j is zero
dp[i][j] = 0;
}
else if (str1.charAt(i - 1) == str2.charAt(j - 1))
{
// When str1[i-1] and str2[j - 1] are same
// Then update dp[i][j] value
dp[i][j] = dp[i - 1][j - 1] + 1;
// Get max value of given parameters
count = maxValue(count, dp[i][j]);
}
else
{
// set zero
dp[i][j] = 0;
}
}
}
// Display result
System.out.print(" Given : " + str1 + " " + str2);
System.out.print("\n Result : " + count + " \n");
}
public static void main(String[] args)
{
// str1 = xycmitimesnxycode str2 = xycstimesce
// times
// Result : 5
// str1 = abxicde str2 = xyzavbicdn
// icd
// Result : 3
}
}``````

#### Output

`````` Given : xycmitimesnxycode xycstimesce
Result : 5
Given : abxicde xyzavbicdn
Result : 3``````
``````// Include header file
#include <iostream>
#include <string>

using namespace std;
/*
C++ program for
Longest common substring using dynamic programming
*/
class CommonSubstring
{
public: int maxValue(int a, int b)
{
if (a > b)
{
return a;
}
return b;
}
void longestCommonSubstring(string str1, string str2)
{
// Get the length of given string
int n = str1.length();
int m = str2.length();
if (n <= 0 || m <= 2)
{
return;
}
// Use to collect common substring result
int dp[n + 1][m + 1];
int count = 0;
// Execute loop through by size of str1
for (int i = 0; i <= n; ++i)
{
// Execute loop through by size of str2
for (int j = 0; j <= m; ++j)
{
if (i == 0 || j == 0)
{
// Set default value when i and j is zero
dp[i][j] = 0;
}
else if (str1[i - 1] == str2[j - 1])
{
// When str1[i-1] and str2[j - 1] are same
// Then update dp[i][j] value
dp[i][j] = dp[i - 1][j - 1] + 1;
// Get max value of given parameters
count = this->maxValue(count, dp[i][j]);
}
else
{
// set zero
dp[i][j] = 0;
}
}
}
// Display result
cout << " Given : " << str1 << " " << str2;
cout << "\n Result : " << count << " \n";
}
};
int main()
{
// str1 = xycmitimesnxycode str2 = xycstimesce
// times
// Result : 5
// str1 = abxicde str2 = xyzavbicdn
// icd
// Result : 3
return 0;
}``````

#### Output

`````` Given : xycmitimesnxycode xycstimesce
Result : 5
Given : abxicde xyzavbicdn
Result : 3``````
``````// Include namespace system
using System;
/*
Csharp program for
Longest common substring using dynamic programming
*/
public class CommonSubstring
{
public int maxValue(int a, int b)
{
if (a > b)
{
return a;
}
return b;
}
public void longestCommonSubstring(String str1, String str2)
{
// Get the length of given string
int n = str1.Length;
int m = str2.Length;
if (n <= 0 || m <= 2)
{
return;
}
// Use to collect common substring result
int[,] dp = new int[n + 1,m + 1];
int count = 0;
// Execute loop through by size of str1
for (int i = 0; i <= n; ++i)
{
// Execute loop through by size of str2
for (int j = 0; j <= m; ++j)
{
if (i == 0 || j == 0)
{
// Set default value when i and j is zero
dp[i,j] = 0;
}
else if (str1[i - 1] == str2[j - 1])
{
// When str1[i-1] and str2[j - 1] are same
// Then update dp[i,j] value
dp[i,j] = dp[i - 1,j - 1] + 1;
// Get max value of given parameters
count = this.maxValue(count, dp[i,j]);
}
else
{
// set zero
dp[i,j] = 0;
}
}
}
// Display result
Console.Write(" Given : " + str1 + " " + str2);
Console.Write("\n Result : " + count + " \n");
}
public static void Main(String[] args)
{
// str1 = xycmitimesnxycode str2 = xycstimesce
// times
// Result : 5
// str1 = abxicde str2 = xyzavbicdn
// icd
// Result : 3
}
}``````

#### Output

`````` Given : xycmitimesnxycode xycstimesce
Result : 5
Given : abxicde xyzavbicdn
Result : 3``````
``````package main

import "fmt"
/*
Go program for
Longest common substring using dynamic programming
*/

func maxValue(a, b int) int {
if a > b {
return a
}
return b
}
func longestCommonSubstring(str1, str2 string) {
// Get the length of given string
var n int = len(str1)
var m int = len(str2)
if n <= 0 || m <= 2 {
return
}
// Use to collect common substring result
var dp = make([][]int,n+1)

for i:=0 ; i <= n; i++ {
dp[i] = make([]int,m+1)
}
var count int = 0
// Execute loop through by size of str1
for i := 0 ; i <= n ; i++ {
// Execute loop through by size of str2
for j := 0 ; j <= m ; j++ {
if i == 0 || j == 0 {
// Set default value when i and j is zero
dp[i][j] = 0
} else if str1[i - 1] == str2[j - 1] {
// When str1[i-1] and str2[j - 1] are same
// Then update dp[i][j] value
dp[i][j] = dp[i - 1][j - 1] + 1
// Get max value of given parameters
count = maxValue(count, dp[i][j])
} else {
// set zero
dp[i][j] = 0
}
}
}
// Display result
fmt.Print(" Given : ", str1, " ", str2)
fmt.Print("\n Result : ", count, " \n")
}
func main() {

// str1 = xycmitimesnxycode str2 = xycstimesce
// times
// Result : 5
longestCommonSubstring("xycmitimesnxycode", "xycstimesce")
// str1 = abxicde str2 = xyzavbicdn
// icd
// Result : 3
longestCommonSubstring("abxicde", "xyzavbicdn")
}``````

#### Output

`````` Given : xycmitimesnxycode xycstimesce
Result : 5
Given : abxicde xyzavbicdn
Result : 3``````
``````<?php
/*
Php program for
Longest common substring using dynamic programming
*/
class CommonSubstring
{
public	function maxValue(\$a, \$b)
{
if (\$a > \$b)
{
return \$a;
}
return \$b;
}
public	function longestCommonSubstring(\$str1, \$str2)
{
// Get the length of given string
\$n = strlen(\$str1);
\$m = strlen(\$str2);
if (\$n <= 0 || \$m <= 2)
{
return;
}
// Use to collect common substring result
\$dp = array_fill(0, \$n + 1, array_fill(0, \$m + 1, 0));
\$count = 0;
// Execute loop through by size of str1
for (\$i = 0; \$i <= \$n; ++\$i)
{
// Execute loop through by size of str2
for (\$j = 0; \$j <= \$m; ++\$j)
{
if (\$i == 0 || \$j == 0)
{
// Set default value when i and j is zero
\$dp[\$i][\$j] = 0;
}
else if (\$str1[\$i - 1] == \$str2[\$j - 1])
{
// When str1[i-1] and str2[j - 1] are same
// Then update dp[i][j] value
\$dp[\$i][\$j] = \$dp[\$i - 1][\$j - 1] + 1;
// Get max value of given parameters
\$count = \$this->maxValue(\$count, \$dp[\$i][\$j]);
}
else
{
// set zero
\$dp[\$i][\$j] = 0;
}
}
}
// Display result
echo(" Given : ".\$str1.
" ".\$str2);
echo("\n Result : ".\$count.
" \n");
}
}

function main()
{
// str1 = xycmitimesnxycode str2 = xycstimesce
// times
// Result : 5
// str1 = abxicde str2 = xyzavbicdn
// icd
// Result : 3
}
main();``````

#### Output

`````` Given : xycmitimesnxycode xycstimesce
Result : 5
Given : abxicde xyzavbicdn
Result : 3``````
``````/*
Node JS program for
Longest common substring using dynamic programming
*/
class CommonSubstring
{
maxValue(a, b)
{
if (a > b)
{
return a;
}
return b;
}
longestCommonSubstring(str1, str2)
{
// Get the length of given string
var n = str1.length;
var m = str2.length;
if (n <= 0 || m <= 2)
{
return;
}
// Use to collect common substring result
var dp = Array(n + 1).fill(0).map(() => new Array(m + 1).fill(0));
var count = 0;
// Execute loop through by size of str1
for (var i = 0; i <= n; ++i)
{
// Execute loop through by size of str2
for (var j = 0; j <= m; ++j)
{
if (i == 0 || j == 0)
{
// Set default value when i and j is zero
dp[i][j] = 0;
}
else if (str1.charAt(i - 1) == str2.charAt(j - 1))
{
// When str1[i-1] and str2[j - 1] are same
// Then update dp[i][j] value
dp[i][j] = dp[i - 1][j - 1] + 1;
// Get max value of given parameters
count = this.maxValue(count, dp[i][j]);
}
else
{
// set zero
dp[i][j] = 0;
}
}
}
// Display result
process.stdout.write(" Given : " + str1 + " " + str2);
process.stdout.write("\n Result : " + count + " \n");
}
}

function main()
{
// str1 = xycmitimesnxycode str2 = xycstimesce
// times
// Result : 5
// str1 = abxicde str2 = xyzavbicdn
// icd
// Result : 3
}
main();``````

#### Output

`````` Given : xycmitimesnxycode xycstimesce
Result : 5
Given : abxicde xyzavbicdn
Result : 3``````
``````#    Python 3 program for
#    Longest common substring using dynamic programming
class CommonSubstring :
def maxValue(self, a, b) :
if (a > b) :
return a

return b

def longestCommonSubstring(self, str1, str2) :
#  Get the length of given string
n = len(str1)
m = len(str2)
if (n <= 0 or m <= 2) :
return

#  Use to collect common substring result
dp = [[0] * (m + 1) for _ in range(n + 1) ]
count = 0
i = 0
#  Execute loop through by size of str1
while (i <= n) :
j = 0
#  Execute loop through by size of str2
while (j <= m) :
if (i == 0 or j == 0) :
#  Set default value when i and j is zero
dp[i][j] = 0
elif (str1[i - 1] == str2[j - 1]) :
#  When str1[i-1] and str2[j - 1] are same
#  Then update dp[i][j] value
dp[i][j] = dp[i - 1][j - 1] + 1
#  Get max value of given parameters
count = self.maxValue(count, dp[i][j])
else :
#  set zero
dp[i][j] = 0

j += 1

i += 1

#  Display result
print(" Given : ", str1 ," ", str2, end = "")
print("\n Result : ", count ," ")

def main() :
#  str1 = xycmitimesnxycode str2 = xycstimesce
#  times
#  Result : 5
#  str1 = abxicde str2 = xyzavbicdn
#  icd
#  Result : 3

if __name__ == "__main__": main()``````

#### Output

`````` Given :  xycmitimesnxycode   xycstimesce
Result :  5
Given :  abxicde   xyzavbicdn
Result :  3``````
``````#    Ruby program for
#    Longest common substring using dynamic programming
class CommonSubstring
def maxValue(a, b)
if (a > b)
return a
end

return b
end

def longestCommonSubstring(str1, str2)
#  Get the length of given string
n = str1.length
m = str2.length
if (n <= 0 || m <= 2)
return
end

#  Use to collect common substring result
dp = Array.new(n + 1) {Array.new(m + 1) {0}}
count = 0
i = 0
#  Execute loop through by size of str1
while (i <= n)
j = 0
#  Execute loop through by size of str2
while (j <= m)
if (i == 0 || j == 0)
#  Set default value when i and j is zero
dp[i][j] = 0
elsif (str1[i - 1] == str2[j - 1])
#  When str1[i-1] and str2[j - 1] are same
#  Then update dp[i][j] value
dp[i][j] = dp[i - 1][j - 1] + 1
#  Get max value of given parameters
count = self.maxValue(count, dp[i][j])
else

#  set zero
dp[i][j] = 0
end

j += 1
end

i += 1
end

#  Display result
print(" Given : ", str1 ," ", str2)
print("\n Result : ", count ," \n")
end

end

def main()
#  str1 = xycmitimesnxycode str2 = xycstimesce
#  times
#  Result : 5
#  str1 = abxicde str2 = xyzavbicdn
#  icd
#  Result : 3
end

main()``````

#### Output

`````` Given : xycmitimesnxycode xycstimesce
Result : 5
Given : abxicde xyzavbicdn
Result : 3
``````
``````/*
Scala program for
Longest common substring using dynamic programming
*/
class CommonSubstring()
{
def maxValue(a: Int, b: Int): Int = {
if (a > b)
{
return a;
}
return b;
}
def longestCommonSubstring(str1: String, str2: String): Unit = {
// Get the length of given string
var n: Int = str1.length();
var m: Int = str2.length();
if (n <= 0 || m <= 2)
{
return;
}
// Use to collect common substring result
var dp: Array[Array[Int]] = Array.fill[Int](n + 1, m + 1)(0);
var count: Int = 0;
var i: Int = 0;
// Execute loop through by size of str1
while (i <= n)
{
var j: Int = 0;
// Execute loop through by size of str2
while (j <= m)
{
if (i == 0 || j == 0)
{
// Set default value when i and j is zero
dp(i)(j) = 0;
}
else if (str1.charAt(i - 1) == str2.charAt(j - 1))
{
// When str1[i-1] and str2[j - 1] are same
// Then update dp[i][j] value
dp(i)(j) = dp(i - 1)(j - 1) + 1;
// Get max value of given parameters
count = maxValue(count, dp(i)(j));
}
else
{
// set zero
dp(i)(j) = 0;
}
j += 1;
}
i += 1;
}
// Display result
print(" Given : " + str1 + " " + str2);
print("\n Result : " + count + " \n");
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: CommonSubstring = new CommonSubstring();
// str1 = xycmitimesnxycode str2 = xycstimesce
// times
// Result : 5
// str1 = abxicde str2 = xyzavbicdn
// icd
// Result : 3
}
}``````

#### Output

`````` Given : xycmitimesnxycode xycstimesce
Result : 5
Given : abxicde xyzavbicdn
Result : 3``````
``````import Foundation;
/*
Swift 4 program for
Longest common substring using dynamic programming
*/
class CommonSubstring
{
func maxValue(_ a: Int, _ b: Int) -> Int
{
if (a > b)
{
return a;
}
return b;
}
func longestCommonSubstring(_ s1: String, _ s2: String)
{
// Get the length of given string
let n: Int = s1.count;
let m: Int = s2.count;
let str1 = Array(s1);
let str2 = Array(s2);
if (n <= 0 || m <= 2)
{
return;
}
// Use to collect common substring result
var dp: [
[Int]
] = Array(repeating: Array(repeating: 0, count: m + 1), count: n + 1);
var count: Int = 0;
var i: Int = 0;
// Execute loop through by size of str1
while (i <= n)
{
var j: Int = 0;
// Execute loop through by size of str2
while (j <= m)
{
if (i == 0 || j == 0)
{
// Set default value when i and j is zero
dp[i][j] = 0;
}
else if (str1[i - 1] == str2[j - 1])
{
// When str1[i-1] and str2[j - 1] are same
// Then update dp[i][j] value
dp[i][j] = dp[i - 1][j - 1] + 1;
// Get max value of given parameters
count = self.maxValue(count, dp[i][j]);
}
else
{
// set zero
dp[i][j] = 0;
}
j += 1;
}
i += 1;
}
// Display result
print(" Given : ", s1 ," ", s2, terminator: "");
print("\n Result : ", count ," ");
}
}
func main()
{
// str1 = xycmitimesnxycode str2 = xycstimesce
// times
// Result : 5
// str1 = abxicde str2 = xyzavbicdn
// icd
// Result : 3
}
main();``````

#### Output

`````` Given :  xycmitimesnxycode   xycstimesce
Result :  5
Given :  abxicde   xyzavbicdn
Result :  3``````
``````/*
Kotlin program for
Longest common substring using dynamic programming
*/
class CommonSubstring
{
fun maxValue(a: Int, b: Int): Int
{
if (a > b)
{
return a;
}
return b;
}
fun longestCommonSubstring(str1: String, str2: String): Unit
{
// Get the length of given string
val n: Int = str1.length;
val m: Int = str2.length;
if (n <= 0 || m <= 2)
{
return;
}
// Use to collect common substring result
var dp: Array < Array < Int >> = Array(n + 1)
{
Array(m + 1)
{
0
}
};
var count: Int = 0;
var i: Int = 0;
// Execute loop through by size of str1
while (i <= n)
{
var j: Int = 0;
// Execute loop through by size of str2
while (j <= m)
{
if (i == 0 || j == 0)
{
// Set default value when i and j is zero
dp[i][j] = 0;
}
else if (str1.get(i - 1) == str2.get(j - 1))
{
// When str1[i-1] and str2[j - 1] are same
// Then update dp[i][j] value
dp[i][j] = dp[i - 1][j - 1] + 1;
// Get max value of given parameters
count = this.maxValue(count, dp[i][j]);
}
else
{
// set zero
dp[i][j] = 0;
}
j += 1;
}
i += 1;
}
// Display result
print(" Given : " + str1 + " " + str2);
print("\n Result : " + count + " \n");
}
}
fun main(args: Array < String > ): Unit
{
// str1 = xycmitimesnxycode str2 = xycstimesce
// times
// Result : 5
// str1 = abxicde str2 = xyzavbicdn
// icd
// Result : 3
}``````

#### Output

`````` Given : xycmitimesnxycode xycstimesce
Result : 5
Given : abxicde xyzavbicdn
Result : 3``````

## Resultant Output Explanation

Let's analyze the output of the provided test cases:

```Given: xycmitimesnxycode xycstimesce
Result: 5
```

In the first test case, the longest common substring between "xycmitimesnxycode" and "xycstimesce" is "times." The length of this substring is 5, which is correctly displayed in the output.

```Given: abxicde xyzavbicdn
Result: 3
```

In the second test case, the longest common substring between "abxicde" and "xyzavbicdn" is "icd." The length of this substring is 3, which is correctly displayed in the output.

## Time Complexity

The time complexity of the provided algorithm is O(n * m), where n and m are the lengths of the input strings. This is because the algorithm requires nested loops to compare each character of both strings and update the `dp` array. As a result, the algorithm's execution time grows linearly with the sizes of the input strings.

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.