gistfile1.txt

// NOTE(as): This is like an unordered Rabin-Karp search. We
// use a simple addition without carry (XOR) to (un)mix the
// probabilistic filter for a substring match.
package main

import (
	"fmt"
	"strings"
)

type R uint64

func (r R) mix(b byte) R {
	const (
		x = 183913
		y = 841
		p = 2147483647
	)
	return (R(b)*x+y)%p ^ r
}

func (r R) mixs(s string) R {
	for _, v := range []byte(s) {
		r = r.mix(byte(v))
	}
	return r
}

func main() {
	s := "ABCBABCYCSABCABCBCAXCA"
	t := "ABC"
	hs := R(0).mixs(t)
	ht := R(0).mixs(s[:len(t)])

	m := [][2]int{}
	for i := len(t); i < len(s); i++ {
		if hs == ht {
			m = append(m, [2]int{i - len(t), i})
		}
		hs = hs.mix(s[i-len(t)])
		hs = hs.mix(s[i])
	}

	n := 0
	for _, r := range m {
		if strings.Compare(t, s[r[0]:r[1]]) == 0 {
			n++
		}
	}

	fmt.Println(len(m), n)
}