Ibe10

public class Stringologia {

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

                        if (i == vzorka.length()) {
                                System.out.println("Nasiel sa vyskyt na pozicii " + poz);
                        }
                        poz++;
                }
        }

        public static int prefixovySufix(String s) {
                for (int poz = 1; poz < s.length(); poz++) {
                        boolean zhoda = true;
                        for (int i = 0; poz + i < s.length(); i++) {
                                if (s.charAt(poz + i) != s.charAt(i)) {
                                        zhoda = false;
                                        break;
                                }
                        }
                        if (zhoda) {
                                return s.length() - poz;
                        }
                }
                return 0;
        }

        public static int[] vypocitajPolePS(String vzorka) {
                int[] ps = new int[vzorka.length()+1];
                for (int i=0; i<ps.length; i++)
                        ps[i] = prefixovySufix(vzorka.substring(0, i));

                return ps;
        }

        public static void najdiVyskyty2(String retazec, String vzorka) {
                int[] ps = vypocitajPolePS(vzorka);
                int poz = 0;
                int i = 0;
                while (poz <= retazec.length() - vzorka.length()) {
                        while (i < vzorka.length()
                                        && vzorka.charAt(i) == retazec.charAt(poz + i)) {
                                i++;
                        }

                        if (i == vzorka.length()) {
                                System.out.println("Nasiel sa vyskyt na pozicii " + poz);
                        }

                        // Specialne riesime i=0, pretoze pre prazdny retazec je prefixovy
                        // sufix nedefinovany (nie je to 0, pretoze vtedy by bol prazdny
                        // retazec prefixom prazdneho retazca, co je v rozpore s definiciou)
                        if (i == 0)
                                poz++;
                        else
                                poz = poz + (i - ps[i]);

                        i = ps[i];
                }
        }

        public static void main(String[] args) {
                najdiVyskyty("bacbabababacaab", "ababaca");
                najdiVyskyty2("bacbabababacaab", "ababaca");
                System.out.println(prefixovySufix("ababa"));
        }

}