Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
// 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
}
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")
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment