Skip to content

Instantly share code, notes, and snippets.

@as
Created November 12, 2019 04:03
Show Gist options
  • Save as/009ab790c222d2c061ecba6456386fb7 to your computer and use it in GitHub Desktop.
Save as/009ab790c222d2c061ecba6456386fb7 to your computer and use it in GitHub Desktop.
// 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)
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment