EA 3.3.2 - lgT

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

[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