This is a Python program to find longest common subsequence (LCS) of two strings using dynamic programming with bottom-up approach.
A string r is a subsequence of a string s if r can be obtained from s by dropping zero or more characters from s. A string r is a common subsequence of s and t if r is a subsequence of both s and t. A string r is a longest common subsequence (LCS) of s and t if there is no string that is longer than r and is a common subsequence of s and t. The problem is to find an LCS of two given strings.
1. Two functions are defined, lcs and print_lcs.
2. The function lcs takes two strings u and v as arguments.
3. It creates a 2D table c. c is implemented as a list of lists.
4. c[i][j] will contain the length of an LCS of u[i:] and v[j:] where x[k:] is a substring of string x starting at index k.
5. The function first sets c[i][length of v] = 0 and c[length of u][j] = 0 for all i and j.
6. The other values are computed as c[i][j] = 1 + c[i + 1][j + 1] if u[i] == v[j].
7. If u[i] != v[j], then c[i][j] = max(c[i + 1][j], c[i][j + 1]).
8. It returns the table c.
9. The function print_lcs takes as argument the two strings u, v and the table c as generated above.
10. It prints an LCS of u and v using the table c.
Here is the source code of a Python program to find an LCS of two strings using dynamic programming with bottom-up approach. The program output is shown below.
def lcs(u, v): """Return c where c[i][j] contains length of LCS of u[i:] and v[j:].""" c = [[-1]*(len(v) + 1) for _ in range(len(u) + 1)] for i in range(len(u) + 1): c[i][len(v)] = 0 for j in range(len(v)): c[len(u)][j] = 0 for i in range(len(u) - 1, -1, -1): for j in range(len(v) - 1, -1, -1): if u[i] == v[j]: c[i][j] = 1 + c[i + 1][j + 1] else: c[i][j] = max(c[i + 1][j], c[i][j + 1]) return c def print_lcs(u, v, c): """Print one LCS of u and v using table c.""" i = j = 0 while not (i == len(u) or j == len(v)): if u[i] == v[j]: print(u[i], end='') i += 1 j += 1 elif c[i][j + 1] > c[i + 1][j]: j += 1 else: i += 1 u = input('Enter first string: ') v = input('Enter second string: ') c = lcs(u, v) print('Longest Common Subsequence: ', end='') print_lcs(u, v, c)
1. The user is prompted to enter two strings.
2. lcs is called on the two strings to get the table c.
3. print_lcs is called to display an LCS of the two strings.
Case 1: Enter first string: abcbdab Enter second string: bdcaba Longest Common Subsequence: bdab Case 2: Enter first string: secret Enter second string: ritual Longest Common Subsequence: rt Case 3: Enter first string: treehouse Enter second string: elephant Longest Common Subsequence: eeh
Sanfoundry Global Education & Learning Series – Python Programs.
To practice all Python programs, here is complete set of 150+ Python Problems and Solutions.
- Check Information Technology Books
- Apply for Programming Internship
- Check Python Books
- Practice Programming MCQs
- Apply for Python Internship