Suppose you use the algorithm Length-LCS to find the length of the longest commo
ID: 3673867 • Letter: S
Question
Suppose you use the algorithm Length-LCS to find the length of the longest common sequence between strings S = “BCADB” and T = “BDCBA”. Recall that the algorithm, fills a 5 × 5 table L. Show this table L below.
Length-LCS(S, T)
- If (S[1] = T[1]), then L[1, 1] 1 else L[1, 1] 0
- For j = 2 to m {
- If (S[1] = T[j]), then L[1, j] 1 else L[1, j] L[1, j 1]
}
- For i = 2 to n {
- If (S[i] = T[1]), then L[i, 1] 1 else L[i, 1] L[i 1, 1]
}
- For i = 2 to n {
- For j = 2 to m {
- If (S[i] = T[j]) then L[i, j] 1 + L[i 1, j 1] else L[i, j] max {L[i 1, j], L[i, j 1]}
}
}
- Return(L[n, m])
Explanation / Answer
L(5,5)=3.
1 1 1 1 1 1 1 2 2 2 1 1 2 2 3 1 2 2 2 3 1 2 2 3 3Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.