Longest common substring using dynamic programming
Here given code implementation process.
/*
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
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