Longest common subsequence (LCS) algorithms give a way to decide how similar two given strings are. However, sometimes, we have to filter away some common subsequences that are in some pattern. Here is a problem for you to solve. Given two strings alpha and beta, let gamma to be the longest word satisfying all of the following conditions: gamma is a subsequence of alpha. gamma is a subsequence of beta. gamma does not contain abb. Design an algorithm that finds such a gamma for any given alpha and beta. Also, analyze its time complexity.
function LCSLength(X[1..m], Y[1..n])
C = array(0..m, 0..n)
for i := 0..m
C[i,0] = 0
for j := 0..n
C[0,j] = 0
for i := 1..m
for j := 1..n
if X[i] = Y[j]
C[i,j] := C[i-1,j-1] + 1
else
C[i,j] := max(C[i,j-1], C[i-1,j])
return C[m,n
Screenshot:
after getting the LCS, search for string 'abb'
if 'abb' is substring of obtained LCS
earse 'abb' from LCS.
Note: Please consider my work and give up vote. Thank you :)
Longest common subsequence (LCS) algorithms give a way to decide how similar two given strings are....
2. (40 pts) Let A, B, and C be three strings each n characters long. We want to compute the longest subsequence that is common to all three strings. (a) Let us first consider the following greedy algorithm for this problem. Find the longest common subsequence between any pair of strings, namely, LCS(A, B) LCS(B, C), LCS(A, C). Then, find the longest common subsequence between this LCS and the 3rd string. That is, supposing that the longest common pair wise...
2. (40 pts) Let A, B, and C be three strings each n characters long. We want to compute the longest subsequence that is common to all three strings. (a) Let us first consider the following greedy algorithm for this problem. Find the longest common subsequence between any pair of strings, namely, LCS(A, B). LCS(B,C), LCS(A, C). Then, find the longest common subsequence between this LCS and the 3rd string. That is, supposing that the longest common pair wise subsequence...