import java.lang.StringBuffer;
import java.util.LinkedList;

public class DynamicApproximateMatch {

    public static void main(String[] args) {

        if (args.length < 2) {
            System.err.println("Usage: java DynamicApproximateMatch key text [diff]");
            return;
        }

        String key = args[0];
        /*
        StringBuffer text = new StringBuffer();
        for (int i = 1; i < args.length; i++) {
            text.append(args[i]);
            if (i != args.length-1)
                text.append(" ");
        }
        */
        String text = args[1];

        int k = 0;
        if (args.length == 3)
            k = Integer.valueOf(args[2]);

        char[] P = key.toCharArray();
        char[] T = text.toCharArray();

        System.out.println("P=");
        System.out.println(toStringWithIndex(P));

        System.out.println("T=");
        System.out.println(toStringWithIndex(T));


        System.out.println("Naive");
        int alku = match_naive(T, P);
        if (alku == -1)
            System.out.println("Not found");
        else
            System.out.println("Match: " + new String(T, alku, P.length));

        LinkedList<Integer> ends = approximateMatch(T, P, k);
        System.out.println("Match ends " + ends);

    }


    static String toStringWithIndex(char[] T) {
        int n = T.length;

        StringBuffer s = new StringBuffer((n + 3) * 3);
        for (int i = 0; i < n; i++)
            s.append((int)(i/10));
        s.append("\n");
        for (int i = 0; i < n; i++)
            s.append(i%10);
        s.append("\n");
        for (int i = 0; i < n; i++)
            s.append(T[i]);
        s.append("\n");

        return s.toString();
    }


    
    static int match_naive(char[] T, char[] P) {
        int n = T.length; int m = P.length;
        for (int s = 0; s <= n-m; s++) {
            int i = 0;
            while (i < m && T[s+i] == P[i])
                i++;
            if (i == m)
                return s;
        }
        return -1;
    }

    
    static int min(int a, int b, int c) {
        if (a < b) {
            if (a < c)
                return a;
            else
                return c;
        } else {
            if (b < c)
                return b;
            else
                return c;
        }
    }


    // returns list of end indexes where difference is <= k
    static LinkedList<Integer> approximateMatch(char[] T, char[] P, int k) {
        int n = T.length; int m = P.length;
        int[][] D = new int[m+1][n+1];

        // column 0 contains row index
        for (int i = 0; i <= m; i++)
            D[i][0] = i;

        // row 0 contains zeros
        for (int i = 0; i <= n; i++)
            D[0][i] = 0;

        // In D, strings indexed 1..n
        for (int i = 1; i <= m; i++)
            for (int j = 1; j <= n; j++)
                if (P[i-1] == T[j-1])      // P and T indexed from 0
                    D[i][j] = min(D[i-1][j]+1, D[i][j-1]+1, D[i-1][j-1]);
                else
                    D[i][j] = min(D[i-1][j]+1, D[i][j-1]+1, D[i-1][j-1]+1);

    
        
        // print matrixif you wish
       
        /*
        System.out.println("DynApproxMatchMatrix:");
        System.out.print(". . .");
        for (int j = 0; j < n; j++)
            System.out.print(" " + T[j]);
        System.out.print("\n. .");
        for (int j = 0; j <= n; j++)
            System.out.print(" " + j);
        System.out.println();
        for (int i = 0; i <= m; i++) {
            if (i == 0)
                System.out.print(". " + i);
            else
                System.out.print(P[i-1] + " " + i);
            for (int j = 0; j <= n; j++)
                    System.out.print(" " + D[i][j]);
            System.out.println();
        }
        System.out.println();
        */
        
        

        LinkedList<Integer> L = new LinkedList<Integer>();
        for (int j = 1; j <= n; j++)
            if (D[m][j] <= k)
                L.add(j-1); // T indexes from 0

        return L;
    }

    



} // class