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

public class MjonoLikimHaku {

    public static void main(String[] args) {

        if (args.length < 2) {
            System.err.println("Käyttö: java MjonoLikimHaku avain teksti [ero]");
            return;
        }

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

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

        char[] P = avain.toCharArray();
        char[] T = teksti.toCharArray();

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

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


        System.out.println("Naiivi");
        int alku = match_naive(T, P);
        if (alku == -1)
            System.out.println("Ei löytynyt");
        else
            System.out.println("Löytyi: " + new String(T, alku, P.length));

        LinkedList<Integer> loput = likimaarainenHaku(T, P, k);
        System.out.println("Likim loput (0-alkuisena): " + loput);

    }


    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;
        }
    }


    // palauttaa listan niistä loppukohdista joissa merkkijonossa
    // on korkeintaan k:n merkin ero
    static LinkedList<Integer> likimaarainenHaku(char[] T, char[] P, int k) {
        int n = T.length; int m = P.length;
        int[][] D = new int[m+1][n+1];

        // taulukko D:n 0-sarake sisältää indeksejä,
        // käytännössä alkusiirtymä (alun merkit puuttuvat)
        for (int i = 0; i <= m; i++)
            D[i][0] = i;

        // 0-rivi 0:ia
        for (int i = 0; i <= n; i++)
            D[0][i] = 0;

        // D:ssä merkkijonot 1..n
        for (int i = 1; i <= m; i++)
            for (int j = 1; j <= n; j++)
                if (P[i-1] == T[j-1])      // P ja T 0-alkuisia
                    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);

    
        
        // tulosta taulu jos haluat
       
        /*
        System.out.println("LikimHaunDynTaulu:");
        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 0-alkuinen

        return L;
    }

    



} // class