JUST PART C Thanks in advance Two character strings may have

JUST PART C! Thanks in advance!

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 (MCS) length is 6. Let X = x_1x_2...x_m and Y = y_1y_2... y_n be two character strings. Give a dynamic programming algorithm to find the MCS length for X and Y. Analyze the worst-case running time and space requirements of your algorithm as functions of n and m. Demonstrate your dynamic programming algorithm for finding the MCS length of character strings algorithm and logarithm, by constructing the corresponding dynamic programming tables.

Solution

The C implemetation to find the Maximum common substring between algorithm and logarithm is given as,

#include <stdio.h>
#include <string.h>

int max(int p, int q){
   return p>q ? p:q;
}
int MaximumCommonSubstring(char * X, char * Y){
    int lengthX = strlen(X);
    int lengthY = strlen(Y);

   int MCS[lengthX+1][lengthY+1];

   for (int i=0; i <= lengthX; i++){
       MCS[i][0] = 0;
   }

   for (int j=0; j <= lengthY; j++){
       MCS[0][j] = 0;
   }

   int maxLength = 0;

   for (int i=1; i<= lengthX; i++){
       for (int j=1; j <= lengthY; j++){
           if (X[i] == Y[j]){
               MCS[i][j] = 1 + MCS[i-1][j-1];      
               maxLength = max( maxLength, MCS[i][j] );
           }
           else {
               MCS[i][j] = 0;
           }
   }
   }

   for (int i=0; i<= lengthX; i++){
       printf(\"\ \");
       for (int j=0; j <= lengthY; j++){
           printf(\"%d \", MCS[i][j]);
       }
   }
   return maxLength;
}

int main(void) {
   char *p = \"algorithm\";
   char *q = \"logarithm\";

   printf(\"\ The maximum common substring is : %d\",
           MaximumCommonSubstring(p,q));

   return 0;
}

The output gives the dynamic algorithm table for maximum common substring in the given strings, it is represented as,

0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0
0 0 0 0 0 2 0 0 0 0
0 0 0 0 0 0 3 0 0 0
0 0 0 0 0 0 0 4 0 0
0 0 0 0 0 0 0 0 5 0
0 0 0 0 0 0 0 0 0 6

The maximum common substring is : 6