Write a Python program called LCS such that LCSx y i j compu

Write a Python program called LCS such that LCS(x, y, i, j) computes and returns the length of the longest common substring of x[0 : i + 1] and y[0 : j + 1], with the condition that this common substring must include x[i] and y[j].

Hints: (1) There are two cases to consider (i) x[i] is the same as y[j] and (ii) x[i] is different from y[j]. (2) The “smallest cases” are when i < 0 or j < 0.

LCS does not directly solves our problem yet. Use this function LCS(x, y, i, j) to find the length of longest common substring of x and y.

Solution

def lcs(S1,T1):
    m = len(S1)
    n = len(T1)
    counter = [[0]*(n+1) for x in range(m+1)]
    longest = 0
    lcs_set = set()
    for i in range(m):
        for j in range(n):
            if S1[i] == T1[j]:
                c = counter[i][j] + 1
                counter[i+1][j+1] = c
                if c > longest:
                    lcs_set = set()
                    longest = c
                    lcs_set.add(S1[i-c+1:i+1])
                elif c == longest:
                    lcs_set.add(S1[i-c+1:i+1])

    return lcs_set

def LCS(x,y,i,j):
    return lcs(x[:i+1],y[:j+1])

print(LCS(\"ankitsdfsfd\",\"sdanksdfsdf\",5,5))

Code: