// Week 4 – Naive pattern matching
// Run: java PatternSearch.java
public class PatternSearch {

    static long comparisons;

    // Index of the first occurrence of the pattern in the text, or -1.
    // The pattern is compared at every possible starting position – O(n·m) in the worst case.
    //   Pseudocode (from 1):
    //     For i ← 1 to n − m + 1
    //       j ← 1
    //       While j ≤ m and S[i + j − 1] = P[j] : j ← j + 1
    //       If j > m then Return i
    //     End for
    //     Return 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;
    }

    // Printing every occurrence
    static void findAll(String text, String pattern) {
        int n = text.length(), m = pattern.length();
        System.out.print("occurrences of \"" + pattern + "\": ");
        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 + " comparisons)");

        findAll("abracadabra", "abra");

        // Worst case: searching for "aaab" in an "aaaa...ab" text
        String text = "a".repeat(10_000) + "b";
        String pat = "a".repeat(100) + "b";
        comparisons = 0;
        int pos = naiveSearch(text, pat);
        System.out.printf("Worst case: n=%d, m=%d -> %,d comparisons (≈ n·m = %,d), position: %d%n",
                text.length(), pat.length(), comparisons, (long) text.length() * pat.length(), pos);

        // The built-in indexOf
        System.out.println("\"abracadabra\".indexOf(\"cad\") = " + "abracadabra".indexOf("cad"));
    }
}