fork(5) download
copy 
  1. def lcs_algo(S1, S2, m, n):
  2.     L = [[0 for x in range(n+1)] for x in range(m+1)]
  3.  
  4.     # Building the mtrix in bottom-up way
  5.     for i in range(m+1):
  6.         for j in range(n+1):
  7.             if i == 0 or j == 0:
  8.                 L[i][j] = 0
  9.             elif S1[i-1] == S2[j-1]:
  10.                 L[i][j] = L[i-1][j-1] + 1
  11.             else:
  12.                 L[i][j] = max(L[i-1][j], L[i][j-1])
  13.  
  14.     index = L[m][n]
  15.  
  16.     lcs_algo = [""] * (index+1)
  17.     lcs_algo[index] = ""
  18.  
  19.     i = m
  20.     j = n
  21.     while i > 0 and j > 0:
  22.  
  23.         if S1[i-1] == S2[j-1]:
  24.             lcs_algo[index-1] = S1[i-1]
  25.             i -= 1
  26.             j -= 1
  27.             index -= 1
  28.  
  29.         elif L[i-1][j] > L[i][j-1]:
  30.             i -= 1
  31.         else:
  32.             j -= 1
  33.  
  34.     # Printing the sub sequences
  35.     print("S1 : " + S1 + "\nS2 : " + S2)
  36.     print("LCS: " + "".join(lcs_algo))
  37.  
  38.  
  39. S1 = "ACADB"
  40. S2 = "CBDA"
  41. m = len(S1)
  42. n = len(S2)
  43. lcs_algo(S1, S2, m, n)
  44.  
Success #stdin #stdout 0.01s 7048KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
S1 : ACADB
S2 : CBDA
LCS: CB
https://ideone.com/qi1QBh
language:
Python (cpython 2.7.16)
created:
3 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!