// 4. hét – Naiv mintakeresés
// Futtatás: go run ./h04/patternsearch
package main

import (
	"fmt"
	"strings"
)

var comparisons int

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

// naiveSearch: a minta első előfordulásának indexe, vagy -1 – legrosszabb esetben O(n·m).
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 összehasonlítás)\n",
		naiveSearch("ABABCABAB", "ABC"), comparisons)

	fmt.Println(`"abra" előfordulásai:`, findAll("abracadabra", "abra"))

	text := strings.Repeat("a", 10_000) + "b"
	pat := strings.Repeat("a", 100) + "b"
	comparisons = 0
	pos := naiveSearch(text, pat)
	fmt.Printf("Legrosszabb eset: n=%d, m=%d -> %d összehasonlítás (≈ n·m = %d), pozíció: %d\n",
		len(text), len(pat), comparisons, len(text)*len(pat), pos)

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