Python Program to Find Longest Common Substring using Dynamic Programming with Memoization

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

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. Two functions are defined, lcw and lcw_starting_at.
2. lcw_starting_at takes as arguments two strings u, v; two indexes i, j; and a 2D table c.
3. c is a list of lists where c[i][j] will contain the length of the LCW starting at u[i:] and v[j:] where x[k:] is a substring of string x starting at index k.
4. The function returns the length of the LCW starting at u[i:] and v[j:] and fills in c as smaller subproblems for finding c[i][j] are solved.
5. The table c satisfies c[i][length of v] = 0 and c[length of u][j] = 0 for all i and j.
6. c also satisfies c[i][j] = 1 + c[i + 1][j + 1] if u[i] == v[j] and c[i][j] = 0 otherwise.
7. The function is implemented recursively and as the length of an LCW is found, it is stored in c.
8. If an LCW has already been calculated and stored in c, then it is immediately returned and not calculated again.
9. The function lcw takes two strings u and v as arguments.
10. It initializes a 2D table c as a list of lists.
11. It finds the largest value returned by lcw_starting_at for all i, j and records the indexes for which the largest value is returned.
12. (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 memoization. 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 = [[-1]*(len(v) + 1) for _ in range(len(u) + 1)]
 
    lcw_i = lcw_j = -1
    length_lcw = 0
    for i in range(len(u)):
        for j in range(len(v)):
            temp = lcw_starting_at(u, v, c, i, j)
            if length_lcw < temp:
                length_lcw = temp
                lcw_i = i
                lcw_j = j
 
    return length_lcw, lcw_i, lcw_j
 
 
def lcw_starting_at(u, v, c, i, j):
    """Return length of the LCW starting at u[i:] and v[j:] and fill table c.
 
    c[i][j] contains the length of the LCW at the start of u[i:] and v[j:].
    This function fills in c as smaller subproblems for solving c[i][j] are
    solved."""
    if c[i][j] >= 0:
        return c[i][j]
 
    if i == len(u) or j == len(v):
        q = 0
    elif u[i] != v[j]:
        q = 0
    else:
        q = 1 + lcw_starting_at(u, v, c, i + 1, j + 1)
 
    c[i][j] = q
    return q
 
 
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: director
Enter second string: conductor
Longest Common Subword: ctor
 
Case 2:
Enter first string: abcbdab
Enter second string: bdcaba
Longest Common Subword: ab
 
Case 3:
Enter first string: bisect
Enter second string: trisect
Longest Common Subword: isect

Sanfoundry Global Education & Learning Series – Python Programs.

To practice all Python programs, here is complete set of 150+ Python Problems and Solutions.