A subsequence is a sequence that can be derived from another sequence by deletin

Question

A subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements; e.g. “acef” is a subsequence of “abcdef.” Consider the problem of finding the longest common subsequence of two sequences – this is a task versioning systems like git or cvs often solve. Show that this is a special case of the sequence alignment problem. Then, give a polynomial-time algorithm for finding the longest subsequence common to three sequences. Analyze its running time and argue why it is correct.

Explanation / Answer

code for longest common subsequnce is

#include<iostream>
#include<cstring>
#include<cstdlib>
using namespace std;

void lcs( char *str1, char *str2, int len1, int len2)
{
int str[len1+1][len2+1];

for (int i=0; i<=len1; i++)
{
for (int j=0; j<=len2; j++)
{
if (i == 0 || j == 0)
str[i][j] = 0;
else if (str1[i-1] == str2[j-1])
str[i][j] = str[i-1][j-1] + 1;
else
str[i][j] = max(str[i-1][j], str[i][j-1]);
}
}

int index = str[len1][len2];

char longestCommonSubsequence[index+1];
longestCommonSubsequence[index] = '';

int i = len1, j = len2;
while (i > 0 && j > 0)
{
if (str1[i-1] == str2[j-1])
{
longestCommonSubsequence[index-1] = str1[i-1];
i--; j--; index--;
}

else if (str[i-1][j] > str[i][j-1])
i--;
else
j--;
}
cout << "Longest common subsequence of " << str1 << " and " << str2 << " is " << longestCommonSubsequence<<endl;
}

int main()
{
char str1[] = "yuyuewnnfskfdm";
char str2[] = "khghiejrdmkm";
int len1 = strlen(str1);
int len2 = strlen(str2);
lcs(str1, str2, len1, len2);
return 0;
}

if the length of string is m and length of string is n

then the comlexity of above code is o(mn)

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.