Given two strings x x1x2 xn and y y1y2 ym we wish to find

Given two strings x = x_1x_2 x_n and y = y_1y_2 y_m, we wish to find the length of their longest common substring, that is, the largest k for which there are indices i and j with x_ix_i+1 x_i+k-1 = y_iy_j+1 y_j+k-1. For example, if x = thecatruns and y = acatran, then the longest common substring is catr Write a Python program that solves this problem with running time in O(n^3). 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]. 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. Compare the raw running times of these two Python programs with at least 10 different values of x and y. Write a Python program that finds the length of the longest common subsequence of x and y. For example, if x = thecatruns and y = acatran, then the longest common subsequence is c, a, t, r, n. For this problem, you can define a function lcs(x, y, i, j) to be the length of the longest common subsequence of x[0: i + 1] and y[0: j +1].

Solution

Answer1:

def largest_common_substring(S1,S2):
m = len(S1)
n = len(S2)
counter = [[0]*(n+1) for x in range(m+1)]
largest = 0
lrgest_common_set = set()
for i in range(m):
for j in range(n):
if S1[i] == S2[j]:
c = counter[i][j] + 1
counter[i+1][j+1] = c
if c > largest:
lrgest_common_set = set()
largest = c
lrgest_common_set.add(S1[i-c+1:i+1])
elif c == largest:
lrgest_common_set.add(S1[i-c+1:i+1])

return lrgest_common_set

ret = largest_common_substring(\'acatran\', \'thecatruns\')
for s in ret:
print(s)