def lev(s1, s2):
if len(s1) < len(s2):
return lev(s2, s1)
# len(s1) >= len(s2)
if len(s2) == 0:
return len(s1)
previous_row = range(len(s2) + 1)
for i, c1 in enumerate(s1):
current_row = [i + 1]
for j, c2 in enumerate(s2):
insertions = previous_row[j + 1] + 1 # j+1 instead of j since previous_row and current_row are one character longer
deletions = current_row[j] + 1 # than s2
substitutions = previous_row[j] + (c1 != c2)
current_row.append(min(insertions, deletions, substitutions))
previous_row = current_row
return previous_row[-1]
s1=raw_input()
s2=raw_input()
def printAllLevSteps(s1, s2):
if len(s1) < len(s2):
s1, s2 = s2, s1
chars = set(s2)
while s1 != s2:
oldS1 = s1
for i in range(len(s1)*2):
temp = list(s1)
if i % 2 == 0:
del(temp[i/2]) #Remove char #i from temp
temp = "".join(temp)
if lev(temp, s2) < lev(s1, s2):
s1 = temp
break
if s1 != oldS1: # For some reason before the loop wouldn't stop
break # so I added this and now it's fine. Don't ask.
for char in chars:
temp = list(s1) # Make it into a list
temp[i/2] = char # Make char #i to variable char
temp = "".join(temp) # Convert it to a string
if lev(temp, s2) < lev(s1, s2):
s1 = temp
break
print s1
print "Distance:",lev(s1, s2)
print "Steps:"
printAllLevSteps(s1, s2)
ZGVmIGxldihzMSwgczIpOgogICAgaWYgbGVuKHMxKSA8IGxlbihzMik6CiAgICAgICAgcmV0dXJuIGxldihzMiwgczEpCgogICAgIyBsZW4oczEpID49IGxlbihzMikKICAgIGlmIGxlbihzMikgPT0gMDoKICAgICAgICByZXR1cm4gbGVuKHMxKQogCiAgICBwcmV2aW91c19yb3cgPSByYW5nZShsZW4oczIpICsgMSkKICAgIGZvciBpLCBjMSBpbiBlbnVtZXJhdGUoczEpOgogICAgICAgIGN1cnJlbnRfcm93ID0gW2kgKyAxXQogICAgICAgIGZvciBqLCBjMiBpbiBlbnVtZXJhdGUoczIpOgogICAgICAgICAgICBpbnNlcnRpb25zID0gcHJldmlvdXNfcm93W2ogKyAxXSArIDEgIyBqKzEgaW5zdGVhZCBvZiBqIHNpbmNlIHByZXZpb3VzX3JvdyBhbmQgY3VycmVudF9yb3cgYXJlIG9uZSBjaGFyYWN0ZXIgbG9uZ2VyCiAgICAgICAgICAgIGRlbGV0aW9ucyA9IGN1cnJlbnRfcm93W2pdICsgMSAgICAgICAjIHRoYW4gczIKICAgICAgICAgICAgc3Vic3RpdHV0aW9ucyA9IHByZXZpb3VzX3Jvd1tqXSArIChjMSAhPSBjMikKICAgICAgICAgICAgY3VycmVudF9yb3cuYXBwZW5kKG1pbihpbnNlcnRpb25zLCBkZWxldGlvbnMsIHN1YnN0aXR1dGlvbnMpKQogICAgICAgIHByZXZpb3VzX3JvdyA9IGN1cnJlbnRfcm93CiAKICAgIHJldHVybiBwcmV2aW91c19yb3dbLTFdCgpzMT1yYXdfaW5wdXQoKQpzMj1yYXdfaW5wdXQoKQoKZGVmIHByaW50QWxsTGV2U3RlcHMoczEsIHMyKToKICAgIGlmIGxlbihzMSkgPCBsZW4oczIpOgogICAgICAgIHMxLCBzMiA9IHMyLCBzMQogICAgY2hhcnMgPSBzZXQoczIpCiAgICB3aGlsZSBzMSAhPSBzMjoKICAgICAgICBvbGRTMSA9IHMxCiAgICAgICAgZm9yIGkgaW4gcmFuZ2UobGVuKHMxKSoyKToKICAgICAgICAgICAgdGVtcCA9IGxpc3QoczEpCiAgICAgICAgICAgIGlmIGkgJSAyID09IDA6CiAgICAgICAgICAgICAgICBkZWwodGVtcFtpLzJdKSAjUmVtb3ZlIGNoYXIgI2kgZnJvbSB0ZW1wCiAgICAgICAgICAgIHRlbXAgPSAiIi5qb2luKHRlbXApCiAgICAgICAgICAgIGlmIGxldih0ZW1wLCBzMikgPCBsZXYoczEsIHMyKToKICAgICAgICAgICAgICAgIHMxID0gdGVtcAogICAgICAgICAgICAgICAgYnJlYWsKICAgICAgICAgICAgaWYgczEgIT0gb2xkUzE6ICMgRm9yIHNvbWUgcmVhc29uIGJlZm9yZSB0aGUgbG9vcCB3b3VsZG4ndCBzdG9wCiAgICAgICAgICAgICAgICBicmVhayAgICAgICAjIHNvIEkgYWRkZWQgdGhpcyBhbmQgbm93IGl0J3MgZmluZS4gRG9uJ3QgYXNrLgogICAgICAgICAgICBmb3IgY2hhciBpbiBjaGFyczoKICAgICAgICAgICAgICAgIHRlbXAgPSBsaXN0KHMxKSAgICAgICMgTWFrZSBpdCBpbnRvIGEgbGlzdAogICAgICAgICAgICAgICAgdGVtcFtpLzJdID0gY2hhciAgICAgICAjIE1ha2UgY2hhciAjaSB0byB2YXJpYWJsZSBjaGFyCiAgICAgICAgICAgICAgICB0ZW1wID0gIiIuam9pbih0ZW1wKSAjIENvbnZlcnQgaXQgdG8gYSBzdHJpbmcKICAgICAgICAgICAgICAgIGlmIGxldih0ZW1wLCBzMikgPCBsZXYoczEsIHMyKToKICAgICAgICAgICAgICAgICAgICBzMSA9IHRlbXAKICAgICAgICAgICAgICAgICAgICBicmVhawogICAgICAgIHByaW50IHMxCiAgICAKcHJpbnQgIkRpc3RhbmNlOiIsbGV2KHMxLCBzMikKcHJpbnQgIlN0ZXBzOiIKcHJpbnRBbGxMZXZTdGVwcyhzMSwgczIpCg==