Programming Problem. Consider the shortest common supersequence (SCS) problem. T
ID: 3681941 • Letter: P
Question
Programming Problem. Consider the shortest common supersequence (SCS) problem. The input to the SCS problem is two strings A = A_1...A_M and B = B_1...B_m, and the output in the length of the shortest string that contains both A and B as subsequences. Examples: A = ABCBABA, B = BCAABAB, then the SCS = ABCA ABABA, so the len(SCS) = 9. Given that the recurrence relationship is as follows, implement a dynamic programming algorithm to solve the SCS problem. Let SCS (i, j) be the length of the shortest common supersequence of A[1.,i| and B[1.,j]. Your algorithm must run in O(mn) time. Your program should prompt the user to enter two strings and output the length of the shortest common supersequence, not the actual SCS.Explanation / Answer
/* C program to find length of the shortest supersequence */
#include<stdio.h>
#include<string.h>
/* function to get max of 2 integers */
int max(int a, int b) { return (a > b)? a : b; }
/* Returns length of LCS for X[0..m-1], Y[0..n-1] */
int lcs( char *X, char *Y, int m, int n);
/* Function to find length of the shortest supersequence of X and Y. */
int shortestSuperSequence(char *X, char *Y)
{
int m = strlen(X), n = strlen(Y);
int l = lcs(X, Y, m, n); // find lcs
// Result is sum of input string lengths - length of lcs
return (m + n - l);
}
/* Returns length of LCS for X[0..m-1], Y[0..n-1] */
int lcs( char *X, char *Y, int m, int n)
{
int L[m+1][n+1];
int i, j;
/* Following steps build L[m+1][n+1] in bottom up fashion.
Note that L[i][j] contains length of LCS of X[0..i-1]
and Y[0..j-1] */
for (i=0; i<=m; i++)
{
for (j=0; j<=n; j++)
{
if (i == 0 || j == 0)
L[i][j] = 0;
else if (X[i-1] == Y[j-1])
L[i][j] = L[i-1][j-1] + 1;
else
L[i][j] = max(L[i-1][j], L[i][j-1]);
}
}
/* L[m][n] contains length of LCS for X[0..n-1] and
Y[0..m-1] */
return L[m][n];
}
/* program to test above function */
int main()
{
char x[50],y[50];
//input two strings
printf("enter string1 ");
scanf("%s",x);
printf("enter string2 ");
scanf("%s",y);
printf("Length of the shortest supersequence is %d ",
shortestSuperSequence(x, y));
return 0;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.