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)
{
CommonSubstring task = new CommonSubstring();
// str1 = xycmitimesnxycode str2 = xycstimesce
// times
// Result : 5
task.longestCommonSubstring("xycmitimesnxycode", "xycstimesce");
// str1 = abxicde str2 = xyzavbicdn
// icd
// Result : 3
task.longestCommonSubstring("abxicde", "xyzavbicdn");
}
}
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()
{
CommonSubstring *task = new CommonSubstring();
// str1 = xycmitimesnxycode str2 = xycstimesce
// times
// Result : 5
task->longestCommonSubstring("xycmitimesnxycode", "xycstimesce");
// str1 = abxicde str2 = xyzavbicdn
// icd
// Result : 3
task->longestCommonSubstring("abxicde", "xyzavbicdn");
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)
{
CommonSubstring task = new CommonSubstring();
// str1 = xycmitimesnxycode str2 = xycstimesce
// times
// Result : 5
task.longestCommonSubstring("xycmitimesnxycode", "xycstimesce");
// str1 = abxicde str2 = xyzavbicdn
// icd
// Result : 3
task.longestCommonSubstring("abxicde", "xyzavbicdn");
}
}
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()
{
$task = new CommonSubstring();
// str1 = xycmitimesnxycode str2 = xycstimesce
// times
// Result : 5
$task->longestCommonSubstring("xycmitimesnxycode", "xycstimesce");
// str1 = abxicde str2 = xyzavbicdn
// icd
// Result : 3
$task->longestCommonSubstring("abxicde", "xyzavbicdn");
}
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()
{
var task = new CommonSubstring();
// str1 = xycmitimesnxycode str2 = xycstimesce
// times
// Result : 5
task.longestCommonSubstring("xycmitimesnxycode", "xycstimesce");
// str1 = abxicde str2 = xyzavbicdn
// icd
// Result : 3
task.longestCommonSubstring("abxicde", "xyzavbicdn");
}
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() :
task = CommonSubstring()
# str1 = xycmitimesnxycode str2 = xycstimesce
# times
# Result : 5
task.longestCommonSubstring("xycmitimesnxycode", "xycstimesce")
# str1 = abxicde str2 = xyzavbicdn
# icd
# Result : 3
task.longestCommonSubstring("abxicde", "xyzavbicdn")
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()
task = CommonSubstring.new()
# str1 = xycmitimesnxycode str2 = xycstimesce
# times
# Result : 5
task.longestCommonSubstring("xycmitimesnxycode", "xycstimesce")
# str1 = abxicde str2 = xyzavbicdn
# icd
# Result : 3
task.longestCommonSubstring("abxicde", "xyzavbicdn")
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
task.longestCommonSubstring("xycmitimesnxycode", "xycstimesce");
// str1 = abxicde str2 = xyzavbicdn
// icd
// Result : 3
task.longestCommonSubstring("abxicde", "xyzavbicdn");
}
}
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()
{
let task: CommonSubstring = CommonSubstring();
// str1 = xycmitimesnxycode str2 = xycstimesce
// times
// Result : 5
task.longestCommonSubstring("xycmitimesnxycode", "xycstimesce");
// str1 = abxicde str2 = xyzavbicdn
// icd
// Result : 3
task.longestCommonSubstring("abxicde", "xyzavbicdn");
}
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
{
val task: CommonSubstring = CommonSubstring();
// str1 = xycmitimesnxycode str2 = xycstimesce
// times
// Result : 5
task.longestCommonSubstring("xycmitimesnxycode", "xycstimesce");
// str1 = abxicde str2 = xyzavbicdn
// icd
// Result : 3
task.longestCommonSubstring("abxicde", "xyzavbicdn");
}
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.
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.
New Comment