C10

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class StringologickeAlgoritmy {

        public static void najdiVyskyty(String retazec, String vzorka) {
                int poz = 0;
                while (poz < retazec.length() - vzorka.length()) {
                        int i = 0;
                        while (vzorka.charAt(i) == retazec.charAt(poz + i)) {
                                i++;
                                if (i == vzorka.length()) {
                                        System.out.println(poz);
                                        break;
                                }
                        }

                        poz++;
                }
        }

        public static Map<Character,Integer[]> failureTab(String s){
                Map<Character,Integer[]> failureTabulka = new HashMap<Character, Integer[]>();

                for(int i = 0;i<s.length();i++){
                        if (!failureTabulka.containsKey(s.charAt(i))){
                                failureTabulka.put(s.charAt(i), new Integer[s.length()]);
                        }
                }


                for (Character z : failureTabulka.keySet()) {
                        Integer[] pole = failureTabulka.get(z);
                        for(int i = 0;i<pole.length;i++){
                                if(s.charAt(i)==z)pole[i]=0;
                                else{
                                        String pomocny = s.substring(0,i)+z;
                                        pole[i]=i+1-prefixovySufix(pomocny);

                                }
                        }

                }
                return failureTabulka;
        }

        public static int prefixovySufix(String s) {
                int max = 0;
                for (int i = 0; i < s.length(); i++) {
                        for (int j = 0; j < i; j++) {
                                if (s.charAt(j) != s.charAt(s.length() - i + j))
                                        break;
                                if (i - 1 == j) {
                                        max=i;
                                }
                        }
                }
                return max;
        }
        public static void KMP(String vzor, String retazec){
                 int poz = 0;
                 int i = 0;
                 Map<Character,Integer[]> failureTabulka = failureTab(vzor);
             while (poz < retazec.length() - vzor.length()) {

                     while (vzor.charAt(i) == retazec.charAt(poz + i)) {
                             i++;
                             if (i == vzor.length()) {
                                 System.out.println(poz);
                                 return;
                         }
                     }
                     if(failureTabulka.containsKey(retazec.charAt(poz+i))){
                        poz+= failureTabulka.get(retazec.charAt(poz+i))[i];
                        i=i-failureTabulka.get(retazec.charAt(poz+i))[i]+1;
                     }else{
                         poz+=i+1;
                         i=0;
                     }
             }

        }
        public static void main(String[] args) {
                najdiVyskyty("abcdaabababcdababcdabcabcda", "abcd"); // 0,9,15,22
                System.out.println(prefixovySufix("abababa"));
                Map<Character,Integer[]> failureTabulka = failureTab("ababaca");
                for (Character z : failureTabulka.keySet()) {
                        System.out.println(z+": " + Arrays.toString(failureTabulka.get(z)));

                }
                KMP("ababaca","bacbabababacaab");
        }

}