Python Program to Find Longest Common Substring using Dynamic Programming with Bottom-Up Approach

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.