Longest Common Subsequence
Subsequences
Example
Original String : ABCDEFGHIJK
Subsequence : ACEGIJK (ABCDEFGHIJK), DFGHK (ABCDEFGHIJK)
Not subsequence : DAGH
Poor Approach
- 각 char마다 포함 여부 계산 ... 2^n subsequences.
- If Y is of length m, the time complexity is O(2^n * m)
DP Approach
Analysis of LCS Algorithm
Solution
- The final answer is contained in L[n, m].
- The subsequence can be recovered from the table by backtracking.
We have two nested loops
- The outer one iterates n times.
- The inner one iterates m times.
- A constant amount of work is done inside each iteration of the inner loop.
- Thus, the total running time is O(mn).
Pseudocode of LCS Alg
