// Week 4 – Naive pattern matching
// Run: go run ./w04/patternsearch
package main

import (
	"fmt"
	"strings"
)

var comparisons int

func eq(a, b byte) bool {
	comparisons++
	return a == b
}

// naiveSearch: index of the first occurrence of the pattern, or -1 – O(n·m) in the worst case.
func naiveSearch(text, pattern string) int {
	n, m := len(text), len(pattern)
	for i := 0; i <= n-m; i++ {
		j := 0
		for j < m && eq(text[i+j], pattern[j]) {
			j++
		}
		if j == m {
			return i
		}
	}
	return -1
}

func findAll(text, pattern string) []int {
	var res []int
	n, m := len(text), len(pattern)
	for i := 0; i <= n-m; i++ {
		if text[i:i+m] == pattern {
			res = append(res, i)
		}
	}
	return res
}

func main() {
	comparisons = 0
	fmt.Printf("naiveSearch(\"ABABCABAB\", \"ABC\") = %d  (%d comparisons)\n",
		naiveSearch("ABABCABAB", "ABC"), comparisons)

	fmt.Println(`occurrences of "abra":`, findAll("abracadabra", "abra"))

	text := strings.Repeat("a", 10_000) + "b"
	pat := strings.Repeat("a", 100) + "b"
	comparisons = 0
	pos := naiveSearch(text, pat)
	fmt.Printf("Worst case: n=%d, m=%d -> %d comparisons (≈ n·m = %d), position: %d\n",
		len(text), len(pat), comparisons, len(text)*len(pat), pos)

	fmt.Println(`strings.Index("abracadabra", "cad") =`, strings.Index("abracadabra", "cad"))
}