4226.sagews

def listAt(list,i):
    return list[i-1]
    
def lgT(x,y):
    m = len(x)
    n = len(y)
    l = matrix(m+1,n+1) # bereits mit 0 initialisiert
        
    for i in [1..m]:
        for j in [1..n]:
            if(listAt(x,i)==listAt(y,j)):
                l[i,j] = l[i-1,j-1]+1
            else:
                l[i,j] = max(l[i-1,j],l[i,j-1])

    #debug:
    print l
    
    return l[m,n]

var('a,b,c,d')  # damit a,b,c und d als math. variablen verwendet werden können
                # und nicht explizit als characters 'a','b','c' und 'd' angegeben werden müssen

X = [a,b,c,b,d,a,b]
Y = [b,d,c,a,b,a]
print lgT(X,Y)

[0 0 0 0 0 0 0] [0 0 0 0 1 1 1] [0 1 1 1 1 2 2] [0 1 1 2 2 2 2] [0 1 1 2 2 3 3] [0 1 2 2 2 3 3] [0 1 2 2 3 3 4] [0 1 2 2 3 4 4] 4