This is a Python program to find longest common substring or subword (LCW) of two strings using dynamic programming with bottom-up approach.

A string r is a substring or subword of a string s if r is contained within s. A string r is a common substring of s and t if r is a substring of both s and t. A string r is a longest common substring or subword (LCW) of s and t if there is no string that is longer than r and is a common substring of s and t. The problem is to find an LCW of two given strings.

1. The function lcw is defined.

2. It 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 LCW starting at 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] and c[i][j] = 0 otherwise

7. This is done starting at the bottom row.

8. The largest entry in c and its position is kept track of.

9. (l, i, j) is returned where l is the length of an LCW of the strings u, v where the LCW starts at index i in u and index j in v.

Here is the source code of a Python program to find an LCW of two strings using dynamic programming with bottom-up approach. The program output is shown below.

def lcw(u, v): """Return length of an LCW of strings u and v and its starting indexes. (l, i, j) is returned where l is the length of an LCW of the strings u, v where the LCW starts at index i in u and index j in v. """ # c[i][j] will contain the length of the LCW at the start 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 lcw_i = lcw_j = -1 length_lcw = 0 for i in range(len(u) - 1, -1, -1): for j in range(len(v)): if u[i] != v[j]: c[i][j] = 0 else: c[i][j] = 1 + c[i + 1][j + 1] if length_lcw < c[i][j]: length_lcw = c[i][j] lcw_i = i lcw_j = j return length_lcw, lcw_i, lcw_j u = input('Enter first string: ') v = input('Enter second string: ') length_lcw, lcw_i, lcw_j = lcw(u, v) print('Longest Common Subword: ', end='') if length_lcw > 0: print(u[lcw_i:lcw_i + length_lcw])

1. The user is prompted to enter two strings.

2. lcw is called on the two strings and the length of an LCW and its starting indexes in the two strings is returned.

3. The LCW is printed.

Case 1: Enter first string: bisect Enter second string: trisect Longest Common Subword: isect Case 2: Enter first string: abcbab Enter second string: bcaba Longest Common Subword: ab Case 3: Enter first string: director Enter second string: conductor Longest Common Subword: ctor

**Sanfoundry Global Education & Learning Series – Python Programs.**

To practice all Python programs, __here is complete set of 150+ Python Problems and Solutions__.

**Related Posts:**

- Check Python Books
- Apply for Programming Internship
- Check Information Technology Books
- Apply for Python Internship
- Practice Programming MCQs