Give the algorithm and define the Subproblems in this case a

Give the algorithm and define the Subproblems in this case and do a also do the runtime analysis of the algorithm

Given two strings r 122 an and y yiy2.- ym, we wish to find the length of their longest common substring, that is, the largest k for which there are indices i and j with Give an algorithm that outputs the positions i and j where the longest common substring starts in each of the strings, and the length k of this longest common substring.

Solution

Algorithm for length of longest common subsequence.

k= Longest_Common_Subsequence_Length(int x[],int n,int y[],int m) ;

Declare an array LCS[1000][1000];

int Longest_Common_Subsequence_Length(int x[],int n,int y[],int m)

{

1: for (i=0 to n)

2: LCS[i][n]

3: for (j=0 to m)

4: LCS[m][j]

5: for(i=n-1 to 0) {

6: for(j=m-1 to 0) {

7: LCS[i][j]=LCS[i+1][j+1] //a matching x[i] to y[j]

8: if(x[i]==y[j])

9: LCS[i][j] =LCS[i][j] +1 // A matching pair is found   

10: if( LCS[i][j+1]>LCS[i][j] )

11: LCS[i][j]=LCS[i][j+1]

// inserting gaps to other two cases

12: if(LCS[i+1][j] > LCS[i][j])

13: LCS[i][j] = LCS[i+1][j]

}

}

14: return LCS[0][0]

}

Subproblem: Recursive solution requires 2ⁿ sub problem calls. This solution checks whenever we want to solve a subproblem, whether we have done it before. If we done it before we look into the table instead of solving the subproblem again and again.

LCS (i,j) = 0 if i= n, j=m

Max{LCS[i][j+1], LCS[i+1][j] if x[i]=y[j]

1+LCS[i+1][j+1] if x[i]==y[j]

Analysis

Total running time = step 1 will run n times + spep 3 m times + Product of running times of two loops(step 5 and step 6)

= n+ n + mn

Therefore Time complexity = O(mn)