Skip to main content

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
Last updated on by Kalkicode




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.

New Comment