import java.util.*;

public class EditDistance implements EditDistanceInterface {

    int c_i, c_d, c_r;
    static int MAX = Integer.MAX_VALUE;
    static int UNDEF = -1;

    public EditDistance (int c_i, int c_d, int c_r) {
        this.c_i = c_i;
        this.c_d = c_d;
        this.c_r = c_r;
    }

    public int[][] getEditDistanceDP(String s1, String s2) {

        int m = s1.length();
        int n = s2.length();

        int[][] dist = new int[m+1][n+1];

        for(int i = 0 ; i <= m; i++ )
            dist[i][0] = i*c_d;

        for(int i = 0 ; i <= n; i++ )
            dist[0][i] = i*c_i;

        for(int i = 1; i <= m; i++)
            for(int j = 1; j <= n ; j++) {
                int temp = dist[i-1][j-1];
                temp += (s1.charAt(i-1) == s2.charAt(j-1))?0:c_r;
                dist[i][j] = Math.min(Math.min(temp,dist[i-1][j]+c_d),dist[i][j-1] + c_i);
            }

        return dist ;
    }



    public List<String> getMinimalEditSequence(String s1, String s2) {

        int m = s1.length();
        int n = s2.length();


        int[][] dist = new int[2][n+1];

        int x=1;
        char[][] ops;
        int[][] dec;

        do{

            x*=2;

            int diff = Math.abs(n-m)+x;
            ops = new char[m+1][Math.min(n+1,2*diff+1)];
            dec = new int[m+1][2];

            for(int i = 0 ; i < m+1; i++) {
                dec[i][0] = Math.max(0,i-diff);
                dec[i][1] = Math.min(n,i+diff);
            }

            for(int j = dec[0][0] ; j <= dec[0][1]; j++ ) {
                dist[0][j] = j*c_i;
                ops[0][j] = 'i';
            }

            for(int i = 1; i <= m; i++) {
                dist[i%2][0] = dist[(i+1)%2][0] + c_d;
                ops[i%2][0] = 'd';

                for(int j = dec[i][0]+1; j<= dec[i][1] ; j++) {
                    //System.out.println(i + " " + j);
                    int temp = dist[(i+1)%2][j-1];
                    char s = 'R';

                    if(s1.charAt(i-1) != s2.charAt(j-1)) {
                        temp+=c_r;
                        s='r';
                    }

                    if(j-i+1 <= diff && dist[(i+1)%2][j] + c_d < temp && dist[(i+1)%2][j] + c_d < dist[i%2][j-1] + c_i) {
                        dist[i%2][j] = dist[(i+1)%2][j] + c_d;
                        s='d';
                    }
                    else if(i-j+1 <=diff && dist[i%2][j-1] + c_i < temp && dist[i%2][j-1] + c_i <= dist[(i+1)%2][j] + c_d){
                        dist[i%2][j] = dist[i%2][j-1] + c_i;
                        s = 'i';
                    }
                    else {
                        dist[i%2][j] = temp;
                    }

                    ops[i][j - dec[i][0]] = s;
                }
            }

        }while(dist[m%2][n]/(c_i + c_d) > x);
        //System.out.println(dist[m%2][n]);
        LinkedList<String> ls = new LinkedList<> ();
        int i = s1.length();
        int j = s2.length();

        while(i !=0 || (j-dec[i][0])>0) {
            //System.out.println(i + " " + j);
            //System.out.println(ops.get(i,j));
            switch(ops[i][j-dec[i][0]]) {
                case 'i':
                    ls.add("insert(" + (i) + "," + s2.charAt(j-1) + ")");
                    j--;
                    break;
                case 'd':
                    ls.add("delete(" + (i-1) +")");
                    i--;
                    break;
                case 'r':
                    ls.add("replace(" + (i-1) + "," + s2.charAt(j-1) + ")");
                    i--;
                    j--;
                    break;
                default:
                    i--;
                    j--;
            }
        }
        return ls;
       }
};