Question

Two character strings may have many common substrings. Substrings are required to be contiguous in the original string. For example, photograph and tomography have several common substrings of length one (i.e., single letters), and common substrings ph, to, and ograph as well as all the substrings of ograph. The maximum common substring length is 6. Let X = X122 . Im and Y = yıy2 - - • Yn be two character strings. Using dynamic programming, design an algorithm to find the maximum common substring length for X and Y using dynamic programming. Please follow the general steps for designing a dynamic programming solution as in Q1 (other than the actual programming part).

Answer 1

Step-by-step explanation:

The following function is written in Java. It takes two strings as parameters and calculates the longest substring between both of them and returns that substring length.

import java.util.*;

class Test

{

public static void main(String[] args)

{

String X = "photograph";

String Y = "tomography";

System.out.println(X + '\\' + Y);

System.out.println("Longest common substring length: " + longestSub(X, Y));

}

static int longestSub(String X, String Y)

{

char[] word1 = X.toCharArray();

char[] word2 = Y.toCharArray();

int length1 = X.length();

int length2 = Y.length();

int substringArray[][] = new int[length1 + 1][length2 + 1];

int longestSubstringLength = 0;

for (int i = 0; i <= length1; i++)

{

for (int j = 0; j <= length2; j++)

{

if (i == 0 || j == 0)

substringArray[i][j] = 0;

else if (word1[i - 1] == word2[j - 1])

{

substringArray[i][j]

= substringArray[i - 1][j - 1] + 1;

longestSubstringLength = Integer.max(longestSubstringLength,

substringArray[i][j]);

}

else

substringArray[i][j] = 0;

}

}

return longestSubstringLength;

}

}