def superSeqRec(x,y):
# versione top-down ricorsiva che calcola la lunghezza minima supersequenza
# e una supersequenza che realizza tale minimo.
# E' esaustiva e prova tutte le possibilita'.
# E' inerentemente esponenziale nel caso pessimo (sequenze con caratteri disgiunti)
# perche' in tal caso il numero di chiamate e' nell'ordine di O(2^(m+n))
# (albero completo di profondita' m+n... anche se su alcuni cammini ci si ferma prima)	
	return superSeqRecAux(x, y, 0, 0)

def superSeqRecAux(x,y,i,j):
# funzione ausiliaria con paramentri ausiliari
# casi base: e' finita una delle due sequenze, torno il rimanente dell'altra 	
	if i==len(x):
		return len(y)-j-1,y[j:]
	if j==len(y):
		return len(x)-i-1,x[i:]
# caso valore uguale: posso prendere quel valore e avanzare su entrambe 		
	if x[i]==y[j]:
		l, s = superSeqRecAux(x, y, i+1, j+1)
		return l+1, x[i]+s
# caso valori diversi: non so quale sia la scelta ottima, provo entrambe... 		
	lx, sx = superSeqRecAux(x, y, i+1, j)
	ly, sy = superSeqRecAux(x, y, i, j+1)
# ... prendo quella che porta al risultato ottimo 		
	if lx < ly:
		return lx+1, x[i]+sx
	else:
		return ly+1, y[j]+sy


def superSeqRecDP(x,y):
# versione top-down ricorsiva con matrice per evitare di ricadere 
# negli stessi casi che dipendono solo dagli indici i e j e sono quindi m * n
# T[i][j] va interpretato come la lunghezza della piu' corta supersequenza di x[i:] e y[j:]
# vediamo poi che la matrice delle lunghezze e' sufficiente per ricostruire 
# una (o tutte) le sequenze di lunghezza minima	-- la soluzione non e', in generale, unica
	m, n = len(x), len(y)
	T = [[-1 for _ in range(n+1)] for _ in range(m+1)]
	# possiamo caricare i casi base della versione ricorsiva direttamente
	for i in range (m+1):
		T[i][n]	= m - i
	for j in range(n+1):
		T[m][j] = n - j	
	#T[m][n] = 0
	l = superSeqRecAuxDP(x, y, 0, 0, T)
	return T

def superSeqRecAuxDP(x,y,i,j,T):
# questa e' del tutto analoga alla versione ricorsiva, ma usa la matrice T
# osservate che il caso base, stavolta, e' aver gia' calcolato T[i][j]	
	m, n = len(x), len(y)
	if T[i][j] < 0:
		if x[i]==y[j]:
			T[i][j] = 1 + superSeqRecAuxDP(x, y, i+1, j+1, T)
		else:
			T[i][j] = 1 + min(superSeqRecAuxDP(x, y, i+1, j, T), 
				superSeqRecAuxDP(x, y, i, j+1, T))
	return T[i][j]


def superSeqBU(x,y):
# costruzione bottom-up della matrice: si parte al solito come nella versione ricorsiva 
# dai casi T[i][n] e T[m][j] poi si procede per righe partendo dal basso verso sinistra
# per calcolare T[i][j] devo conoscere T[i+1][j], T[i][j+1] e T[i+1][j+1]
	m, n = len(x), len(y)
	T = [[-1 for _ in range(n+1)] for _ in range(m+1)]
	for i in range(m+1): T[i][n] = m-i	
	for j in range(n+1): T[m][j] = n-j
	for i in range(m-1,-1,-1):
		for j in range(n-1,-1,-1):
	# notare le analogie con il programma ricorsivo		
			if x[i]==y[j]: T[i][j]=T[i+1][j+1]+1 
			else: T[i][j] = 1 + min(T[i+1][j], T[i][j+1])
	return T


def ricostruisci(T, x, y):
# da T posso ricostruire una soluzione ottima:
# scendere di riga significa prendere il prossimo carattere di x
# scendere di colonna significa prendere il prossimo carattere di y
# devo scendere in diagonale solo se x[i]==y[j] 	
	m = len(T)
	n = len(T[1])
	z = []
	i, j = 0, 0
	while i<m-1 or j<n-1:
		# caso caratteri uguali, vado in diagonale
		if i < m-1 and j < n-1 and x[i] == y[j]:
			z.append(x[i])
			i, j = i+1, j+1
		# caratteri diversi: se l'ottimo e' ottenuto a destra, vado a destra...	
		elif i<m and j<n-1 and T[i][j] == T[i][j+1] + 1:
			z.append(y[j])
			j += 1
		else:
		# ... altrimenti vado a sinistra	
			z.append(x[i]) 		
			i += 1
	return z

# funzione di utilita' per stampare la matrice,
# non come lista di liste
def priMt(T):
	for i in range(len(T)):
		for j in range(len(T[i])):
			print T[i][j],
		print	
	print	

# TEST
x = "alberi"
y = "libri"
print superSeqRec(x,y)
T = superSeqBU(x, y)
priMt(T)
print ricostruisci(T, x, y)
T = superSeqRecDP(x, y)
priMt(T)
print ricostruisci(T, x, y)

# caso pessimo per ricorsiva con sequenze
# a valori disgiunti
x = "aaaa"
y = "bbbbbb"
T = superSeqBU(x, y)
priMt(T)
print ricostruisci(T, x, y)
print superSeqRec(x, y)
T = superSeqRecDP(x, y)
priMt(T)
print ricostruisci(T, x, y)