def longer(x, y): if len(x) > len(y): return x else: return y #counts = {} def LCS(x, y): ## if (x,y) not in counts: ## counts[x,y] = 1 ## else: ## counts[x,y] = counts[x,y] + 1 if len(x) == 0 or len(y) == 0: return '' elif x[0] == y[0]: return x[0] + LCS(x[1:], y[1:]) else: return longer(LCS(x, y[1:]), LCS(x[1:], y)) def MemoizedLCS(x, y): table = {} def LCS(x, y): if (x,y) not in table: if len(x) == 0 or len(y) == 0: table[x,y] = '' elif x[0] == y[0]: table[x,y] = x[0] + LCS(x[1:], y[1:]) else: table[x,y] = longer(LCS(x, y[1:]), LCS(x[1:], y)) return table[x,y] return LCS(x, y) def MemoizedCheapest(x, y, insertionCost, deletionCost, replacementCost): table = {} def Cheapest(x, y): if (x,y) not in table: if len(x) == 0: table[x,y] = (len(y)*insertionCost, [('insert',c) for c in y]) elif len(y) == 0: table[x,y] = (len(x)*deletionCost, [('delete',c) for c in x]) elif x[0] == y[0]: cost, operations = Cheapest(x[1:], y[1:]) table[x,y] = (cost, [('retain',x[0])]+operations) else: cost1, ops1 = Cheapest(x, y[1:]) cost2, ops2 = Cheapest(x[1:], y) cost3, ops3 = Cheapest(x[1:], y[1:]) option1 = (cost1+insertionCost, [('insert',y[0])]+ops1) option2 = (cost2+deletionCost, [('delete', x[0])]+ops2) option3 = (cost3+replacementCost, [('replace',x[0],y[0])]+ops3) table[x,y] = min(option1, option2, option3) return table[x,y] return Cheapest(x, y)