import java.util.ArrayList;
import java.util.Scanner;
import java.math.*;

class MinEditDistance
{
    public static void main(String args[])
    {
        Scanner s = new Scanner(System.in);

//      String input1 = s.nextLine();
//      String input2 = s.nextLine();

        String input1 = "abcdefg";
        String input2 = "abcdegg";

//        String input1 = "intention";
//        String input2 = "execution";

//    	String input1 = "naruto's son";
//        String input2 = "boruto's dad";

//        String input1 = "bugs bunny";
//        String input2 = "big chungus";

//        String input1 = "kumakain";
//        String input2 = "kumain";

//        String input1 = "levinstien";
//        String input2 = "levenshtein";

//        String input1 = "leviathan";
//        String input2 = "levenshtein";

//        String input1 = "ATGCATCCCATGAC";
//        String input2 = "TCTATATCCGT";

//        String input1 = "AGGCTATCACCTGACCTCCAGGCCGATGCCCACCTGG";
//        String input2 = "TAGCTATCACGACCGCGGTCGATTTGCCCGACGGTCC";

        int m = input1.length();
        int n = input2.length();

        //initialize table
        int DP[][] = new int[m+1][n+1];
        ArrayList<Character> BT = new ArrayList<Character>();
        ArrayList<Character> BT2 = new ArrayList<Character>();

        // populate table
        for (int i=0; i<=m; i++)
        {
            for (int j=0; j<=n; j++)
            {
                if (i==0)
                    DP[i][j] = j;

                else if (j==0)
                    DP[i][j] = i;

                else if (input1.charAt(i-1) == input2.charAt(j-1))
            	{
                	DP[i][j] = Math.min(DP[i][j-1]+1, Math.min(DP[i-1][j]+1, DP[i-1][j-1]+0));  //match
            	}

                else
                {
                	 DP[i][j] = Math.min(DP[i][j-1]+1, Math.min(DP[i-1][j]+1, DP[i-1][j-1]+2));  //mismatch
                }
            }
        }

        //print table
        for (int j = 0; j < n+1; j++)
        {
            for (int i = 0; i < m+1; i++)
                System.out.print(DP[i][j]+"\t");

            System.out.println();
        }

        System.out.println("\n\nDISTANCE: "+DP[m][n]);

        int i = m, j = n;
        while (i != 0 && j != 0)
        {
            if (i>0 && j>0)
            {
            	//both input are not at the end
                if (DP[i-1][j-1] <= DP[i-1][j] && DP[i-1][j-1] <= DP[i][j-1])
                {
                	System.out.println("went to "+DP[i-1][j-1]);
                    System.out.println("\\");
                    BT.add('M');
                    i--;
                    j--;
                }

                else if (DP[i-1][j] >= DP[i][j-1])
                {
                	System.out.println("went to "+DP[i][j-1]);
                    System.out.println("-");
                    BT.add('I');
                    i--;
                }

                else if (DP[i-1][j] <= DP[i][j-1])
                {
                	System.out.println("went to "+DP[i-1][j]);
                	System.out.println("|");
                    BT.add('D');
                    j--;
                }
            }

            else if (i==0)
            {
            	// input m is at the end
                System.out.println("|");
                BT.add('D');
                j--;
            }

            else
            { // input n is at the end
                System.out.println("-");
                BT.add('I');
                i--;
            }
        }

//        System.out.println(BT);

        System.out.println("\nalignment: ");
        for(int x = BT.size()-1; x >= 0; x--)
        	System.out.print(BT.get(x) + " ");

//        System.out.println("\nsteps (from top): ");
//        for(int x = BT.size()-1; x >= 0; x--)
//        	System.out.print(BT2.get(x) + " ");

    }
}