#!/usr/bin/python
# -*- coding: utf-8 *-*

# Usage : python editing_distance.py

def simple_make_table(s1, s2):
    """
Retourne le tableau des distances d'édition entres les préfixes de s1 et s2:
la case (i, j) contient la distance entre s1[0:i] et s2[0:j].
    """
    n1 = len(s1)+1
    n2 = len(s2)+1
    table = [None] * n1

    for i in range(0, n1):
        table[i] = [0] * n2

    for i in range(1, n1):
        table[i][0] = i

    for j in range(1, n2):
        table[0][j] = j

    for i in range(1, n1):
        for j in range(1, n2):
            if s1[i-1] == s2[j-1]:
                e = 0
            else:
                e = 1
            table[i] = min(table[i-1][j]+1, table[i][j-1]+1, table[i-1][j-1]+e)

    return table

def simple_distance(s1, s2):
    return simple_make_table(s1, s2)[len(s1)][len(s2)]

# Un version un peu plus compliquée qui calcule non seulement la distance, mais
# aussi la liste optimale d'opérations d'édition associée.
def make_table(s1, s2):
    """
Retourne le tableau des des tuples (d, p) où à la case (i, j) d est la distance
d'édition de s1[0:i] à s2[0:j] et p est une suite optimale d'opérations menant
de s1[0:i] à s2[0:j].

Les opérations sont codés sur trois caractères : "Oxy" ou O est le nom de
l'opération (I pour Insert, D pour Delete et M pour Mutation, N pour Noop,
aucune opération), x et y sont les paramètres de l'opération.
    """
    n1 = len(s1)+1
    n2 = len(s2)+1
    table = [None] * n1

    for i in range(0, n1):
        table[i] = [0] * n2

    table[0][0] = (0, [])
    for i in range(1, n1):
        o = "D%s " % s1[i-1]
        table[i][0] = (i, [o])

    for j in range(1, n2):
        o = "I%s " % s2[j-1]
        table[0][j] = (j, [o])

    for i in range(1, n1):
        c1 = s1[i-1]
        for j in range(1, n2):
            c2 = s2[j-1]

            t = table[i-1][j-1]
            if c1 == c2:
                d  = t[0]
                o = "N  "
                p = t[1] + [o]
            else:
                d = t[0] + 1
                o = "M%s%s" % (c1, c2)
                p = t[1] + [o]

            t = table[i-1][j]
            d1 = t[0] + 1
            if d1 < d:
                d = d1
                o = "D%s " % c1
                p = t[1] + [o]

            t = table[i][j-1]
            d2 = t[0] + 1
            if d2 < d:
                d = d2
                o = "I%s " % c2
                p = t[1] + [o]

            table[i][j] = (d, p)

    return table

def print_table(s1, s2):
    """
Calcul la table des distances en appelant make_table et affiche celle-ci ;
retourne la table calculée.
    """
    table = make_table(s1, s2)

    n1 = len(s1)
    n2 = len(s2)
    table[0][0] = (0, ["   "])

    # Séparation entre deux lignes du tableu
    sep_line = "+" + ("-" * n1) + ("+" + "-" * max(n2, 6)) * (n2+1) + "+"

    # Première ligne contenant les en-têtes de colonnes ; les colonnes sont
    # séparées par un |
    pad       = " " * max(0, 6 - n2)
    head_line =  "|" + "|".join([" " * (n1)]
                                + ["%s%s%s" % (pad, s2[0:j], " " * (n2-j))
                      for j in range(0, n2+1)]) + "|"
    print sep_line
    print head_line
    print sep_line

    # Toutes les lignes, la première colonne contient les en-têtes de ligne
    pad = " " * max(n2 - 6, 0)
    for i in range(0, n1+1):
        line = "|" + "|".join(["%s%s" % (s1[0:i], " " * (n1-i))]
                              + ["%s%s %2d" % (pad, table[i][j][1][-1],
                                               table[i][j][0])
                                 for j in range(0, n2+1)]) + "|"
        print line
        print sep_line

    return table

def apply_ops(s, ops):
    """
Applique la liste d'opérations d'édition ops à la chaîne s ; si ops a été
calculée par make_table(s, s') alors ceci doit rendre s'.
    """
    i = 0
    # On commence par transformer s en un liste de caractères
    goal = list(s)
    for op in ops:
        if op[0] == "M":
            if goal[i] != op[1]:
                raise ValueError("Invalid mutation: %s" % op)
            goal[i] = op[2]
            i += 1
        elif op[0] == "D":
            if goal[i] != op[1]:
                raise ValueError("Invalid deletion: %s" % op)
            goal[i:] = goal[i+1:]
        elif op[0] == "I":
            goal.insert(i, op[1])
            i += 1
        elif op[0] == "N":
            i += 1
        else:
            raise ValueError("Invalid operation: %s" % op)

    return "".join(goal)

while True:
    s1 = raw_input("Entrer une chaîne : ")
    s2 = raw_input("Et une autre : ")

    if len(s1) == 0 or len(s2) == 0:
        print
        print "Entrer des chaînes non vides"
        print
        continue

    print "Table des distances entre '%s' et '%s' :" % (s1, s2)
    table = print_table(s1, s2)

    ops   =  table[len(s1)][len(s2)][1]
    print
    print "Opérations à appliquer à '%s' pour obtenir '%s' :" % (s1, s2)
    for op in ops[:-1]:
        print "%s, " % op.strip(),
    print ops[-1].strip()

    print
    print "Application des opérations à '%s'," % s1,
    s3 = apply_ops(s1, ops)
    print "ce qui donne : '%s'" % s3

    print
    answer = raw_input("Continuer (o/n) ? ")
    if answer == "n" or answer == "N":
        break