public class Zadanie {
	
	static void generujTablicePrefiksoSufiksow(String wzorzec, int tablicaPrefiksoSufiksow[]){
        int j = 0;
        int i = 1;

        tablicaPrefiksoSufiksow[0] = 0;

        while(i < wzorzec.length()){
            if(wzorzec.charAt(i) == wzorzec.charAt(j)){
                j++;
                tablicaPrefiksoSufiksow[i] = j;
                i++;
            }
            else{
                if(j != 0){
                    j = tablicaPrefiksoSufiksow[j-1];
                }
                else{
                    tablicaPrefiksoSufiksow[i] = j;
                    i++;
                }
            }
        }
    }

    static void wyszukajKMP(String wzorzec, String napis){

        int tablicaPrefiksoSufiksow[] = new int[wzorzec.length()];

        generujTablicePrefiksoSufiksow(wzorzec, tablicaPrefiksoSufiksow);

        int i = 0, j = 0;
        while(i < napis.length()){
            if(wzorzec.charAt(j) == napis.charAt(i)){
                j++; i++;
            }
            if(j == wzorzec.length()){
                System.out.println("Znaleiono wzorzec od indeksu: "  + (i-j));
                j = tablicaPrefiksoSufiksow[j-1];
            }
            else if(i < napis.length() && wzorzec.charAt(j) != napis.charAt(i)){
                if (j != 0){
                    j = tablicaPrefiksoSufiksow[j-1];
                }
                else{
                    i++;
                }
            }
        }
    }

    public static void main(String[] args) {
        wyszukajKMP("AABAA", "BBAABAABAA");
    }
}