Python:not getting Length of longest common subsequence of lists
Question: I tried to implement in LCS in simplest way I can but I am not getting the
right value. Instead of 4 I get . I am not sure whats wrong with my code:

    
    
    X= ['A','B','C','B','D','A','B']
    Y= ['B','D','C','A','B','A','X','Y']
    
    m= len(X)
    n= len(Y)
    c={}
    for i in range(1,m) :
        c[i,0]=0
    
    for j in range(0,n):
        c[0,j]=0
    
    for i in range (1,m):
        for j in range (1,n):
            if X[i]==Y[j]:
                c[i,j]=c[i-1,j-1]+1
            elif c[i-1,j] >= c[i,j-1]:
                c[i,j]=c[i-1,j]
            else:
                c[i,j]=c[i,j-1]
    
    
    print c[m-1,n-1]
    print c
    


Answer: Here is the implementation I used for LCS, it returns `(percent_in_common,
sequence_in_common)`

    
    
    def longest_common_sequence(a,b):
       from collections import deque
    
       n1=len(a)
       n2=len(b)
       if not n1:
          if not n2:
             return 100.0, ''
          return 0.0, ''
       if not n2:
          return 0.0, ''
       previous=deque()
       for i in range(n2):
          previous.append((0,''))
       over = (0,'')
       for i in range(n1):
          left = corner = (0,'')
          for j in range(n2):
             over = previous.popleft()
             if a[i] == b[j]:
                this = corner[0] + 1, corner[1]+a[i]
             else:
                this = max(over,left)
             previous.append(this)
             left, corner = this, over
       return round(200.0*this[0]/(n1+n2),2),this[1]
    

