// 4. hét – Naiv mintakeresés
// Futtatás: java PatternSearch.java
public class PatternSearch {

    static long comparisons;

    // A minta első előfordulásának indexe a szövegben, vagy -1.
    // Minden lehetséges kezdőpozícióra összevetjük a mintát – legrosszabb esetben O(n·m).
    //   Pszeudokód (1-től):
    //     Ciklus i ← 1-től n − m + 1-ig
    //       j ← 1
    //       Ciklus amíg j ≤ m és S[i + j − 1] = P[j] : j ← j + 1
    //       Ha j > m akkor Vissza: i
    //     Ciklus vége
    //     Vissza: 0
    static int naiveSearch(String text, String pattern) {
        int n = text.length(), m = pattern.length();
        for (int i = 0; i <= n - m; i++) {
            int j = 0;
            while (j < m && eq(text.charAt(i + j), pattern.charAt(j))) j++;
            if (j == m) return i;
        }
        return -1;
    }

    static boolean eq(char a, char b) {
        comparisons++;
        return a == b;
    }

    // Az összes előfordulás kiírása
    static void findAll(String text, String pattern) {
        int n = text.length(), m = pattern.length();
        System.out.print("\"" + pattern + "\" előfordulásai: ");
        for (int i = 0; i <= n - m; i++) {
            int j = 0;
            while (j < m && text.charAt(i + j) == pattern.charAt(j)) j++;
            if (j == m) System.out.print(i + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        comparisons = 0;
        System.out.println("naiveSearch(\"ABABCABAB\", \"ABC\") = " + naiveSearch("ABABCABAB", "ABC")
                + "  (" + comparisons + " összehasonlítás)");

        findAll("abracadabra", "abra");

        // Legrosszabb eset: "aaaa...ab" szövegben "aaab" keresése
        String text = "a".repeat(10_000) + "b";
        String pat = "a".repeat(100) + "b";
        comparisons = 0;
        int pos = naiveSearch(text, pat);
        System.out.printf("Legrosszabb eset: n=%d, m=%d -> %,d összehasonlítás (≈ n·m = %,d), pozíció: %d%n",
                text.length(), pat.length(), comparisons, (long) text.length() * pat.length(), pos);

        // A beépített indexOf
        System.out.println("\"abracadabra\".indexOf(\"cad\") = " + "abracadabra".indexOf("cad"));
    }
}