Given two strings x = x_1x_2...x_n and y = y_1y_2...ym, we wish to find the leng

Question

Given two strings x = x_1x_2...x_n and y = y_1y_2...ym, 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_jYj+1...y_j+k-1 For example, if x = theca runs and y = acara, then the longest common substring is cart and the answer, its length, is 4.Write a Python program that solves this problem with running time in 0(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 + l] and y[0: j +1], with the condition that this common substring must include x[i] and y[j]. (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

Explanation / Answer

Ans 1:>

This program give the length of the longest subsequence by brute force method:

x = input()
y = input()
l=0
def lcs_x(x):
length = len(x)
return [x[i:j+1] for i in range(length) for j in range(i,length)]
  

def lcs_y(y):
length = len(y)
return [y[i:j+1] for i in range(length) for j in range(i,length)]
  
sub_seq1=lcs_x(x)
sub_seq2=lcs_y(y)

for i in sub_seq1:
   for j in sub_seq2:
       if i==j and len(i)>l:
           l=len(i)
print(l)

Ans 2:>
This program give the length of the longest subsequence with considering two mwntioned cases:
x = input()
y = input()

def lcs(x,y,i,j):
l=0
sub_seq1= [x[m:n+1] for m in range(i) for n in range(m,i)]
sub_seq2= [y[m:n+1] for m in range(j) for n in range(m,j)]
for m in sub_seq1:
   for n in sub_seq2:
       if m==n and len(m)>l:
           l=len(m)
          
print(l)   

i=len(x)
j=len(y)
if i==j:
   print(i)
if i==0:
   print(j)
if j==0:
   print(i)
if i!=j and i!=0 and j!=0:
   lcs(x,y,i,j)

Ans 5:>
This program works recursively. Function call itself again and again and return the lenght of longest string.

#function
def lcs(x, y, i, j):

if i == 0 or j == 0:
return 0;
elif x[i-1] == y[j-1]:
return 1 + lcs(x, y, i-1, j-1);
else:
return max(lcs(x, y, i, j-1), lcs(x, y, i-1, j));

x = input()
y = input()
print("Length of longest common subsequence is ", lcs(x , y, len(x), len(y)))

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.