robin_karp.go

// This packages provides Rabin-Karp string search.
package robin_karp

const prime = 1456667

// Find tries to find string s in t and returns the index of the first index
// of t where s found. Returns -1 when not found. It implements Rabin-Karp
// algorithm.
func Find(s, t string) int {
	ls := len(s)
	lt := len(t)

	if ls > lt {
		return -1
	}

	hs := 0
	for i := 0; i < ls; i++ {
		hs = hs*prime + int(s[i])
	}

	ht := 0
	for i := 0; i < ls; i++ {
		ht = ht*prime + int(t[i])
	}

	if hs == ht && s == t[:ls] {
		return 0
	}

	for i := 1; i < lt-ls+1; i++ {
		ht -= int(t[i-1]) * pow(prime, ls-1)
		ht = ht*prime + int(t[i+ls-1])
		if hs == ht && s == t[i:i+ls] {
			return i
		}
	}

	return -1
}

func pow(x, y int) int {
	z := 1
	for i := 0; i < y; i++ {
		z *= x
	}
	return z
}

robin_karp_test.go

package robin_karp

import (
	"fmt"
	"testing"
)

type findTest struct {
	s string
	t string
	e int
}

var findTests = []findTest{
	{"h", "hello", 0},
	{"l", "hello", 2},
	{"o", "hello", 4},
	{"a", "hello", -1},
	{"yes", "say yes", 4},
	{"func main", "func", -1},
	{"package main", "package main", 0},
	{"", "", 0},
	{"", "a", 0},
}

func TestFind(t *testing.T) {
	for _, test := range findTests {
		v := Find(test.s, test.t)
		if v != test.e {
			t.Errorf("Expected %d, got %d", test.e, v)
		}
	}
}

func ExampleFind() {
	fmt.Println(Find("e", "hello"))
	fmt.Println(Find("a", "hello"))
	// Output:
	// 1
	// -1
}

func BenchmarkFind(b *testing.B) {
	for i := 0; i < b.N; i++ {
		Find("o", "hello")
	}
}