Расстояние Дамерау между двумя текстами.

damerau.py

def f(s1, s2):
	if not s1 or not s2:
		return len(s1)+len(s2)
	elif s1[-1]==s2[-1]:
		return f(s1[:-1], s2[:-1])
	else:
		#вставка/удаление
		a = min(f(s1[:-1], s2), f(s1, s2[:-1]))
		#замена
		b = f(s1[:-1], s2[:-1])
		return min(a, b)+1

if __name__ == '__main__':
	while 1:
		print(f(input('1: '), input('2: ')))