Boyer-More algorithm, ingests a []byte slice and returns the index of the first occurrence of `substr`. (this is particularly useful for large `substr` values)

boyer-moore.go

package bm

import "bytes"

func BoyerMooreIndex(s, substr []byte) int {
	d := CalculateSlideTable(substr)
	return IndexWithTable(&d, s, substr)
}

func IndexWithTable(d *[256]int, s, substr []byte) int {
	lsub := len(substr)
	ls := len(s)
	switch {
	case lsub == 0:
		return 0
	case lsub > ls:
		return -1
	case lsub == ls:
		if bytes.Compare(s, substr) == 0 {
			return 0
		}
		return -1
	}
	i := 0
	for i+lsub-1 < ls {
		j := lsub - 1
		for ; j >= 0 && s[i+j] == substr[j]; j-- {
		}
		if j < 0 {
			return i
		}

		slid := j - d[s[i+j]]
		if slid < 1 {
			slid = 1
		}
		i += slid
	}
	return -1
}

func CalculateSlideTable(substr []byte) [256]int {
	var d [256]int
	for i := 0; i < 256; i++ {
		d[i] = -1
	}
	for i := 0; i < len(substr); i++ {
		d[substr[i]] = i
	}
	return d
}