fork download
copy 
  1. #
  2. # Longest Common Subsequence
  3. #
  4. # Adrian Statescu <mergesortv@gmail.com>
  5. #
  6. # License MIT
  7.  
  8. import sys
  9.  
  10. def main():
  11.     x = [0,1,5,7,5,4]
  12.     y = [0,2,1,2,3,4,5,2,7]
  13.     n, m = len(x), len(y)
  14.     lcs = [ [0 for i in range(m)] for j in range(n) ]
  15.  
  16.     #for debug
  17.     #print lcs
  18.  
  19.     for i in range(1,n):
  20.         for j in range(1, m):
  21.             if x[i] == y[j]:
  22.                 lcs[i][j] = 1 + lcs[i-1][j-1]
  23.             else:
  24.                 lcs[i][j] = max(lcs[i][j-1], lcs[i-1][j])
  25.     print lcs[n-1][m-1]
  26.  
  27.     i = n - 1
  28.     j = m - 1
  29.     ans = []
  30.  
  31.     while i != 0 and j!= 0:
  32.         if(x[i] == y[j]):
  33.            ans.append(x[i])
  34.            i = i - 1
  35.            j = j - 1
  36.         else:
  37.             if lcs[i][j-1] < lcs[i-1][j]:
  38.                 i = i - 1
  39.             else:
  40.                 j = j - 1
  41.     while len(ans) != 0:          
  42.           x = ans.pop()
  43.           sys.stdout.write(str(x) + " ")
  44.  
  45.     print ""
  46.  
  47. main()
Success #stdin #stdout 0.01s 7124KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
3
1 5 7
https://ideone.com/aoessx
Longest Common Subsequence in Python language.
language:
Python (cpython 2.7.16)
created:
4 years ago
visibility:
secret

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!