Rabin Karp Algorithm
In computer science, the Rabin – Karp algorithm or Karp – Rabin algorithm is a string-searching algorithm created by Richard M. Karp and Michael O. Rabin (1987)In contrast, the Aho – Corasick algorithm can find all matches of multiple shapes in worst-case time and space linear in the input length and the number of matches (instead of the total length of the matches).
package RabinKarp
import "hash/adler32"
import (
"math/rand"
"testing"
"time"
)
func calculateHash(text string) uint32 {
return adler32.Checksum([]byte(text))
}
func RabinKarp(text, pattern string) int {
textLength := len(text)
patternLength := len(pattern)
if patternLength > textLength {
return -1
}
for i := 0; i < textLength-patternLength+1; i++ {
if calculateHash(pattern) != calculateHash(text[i:i+patternLength]) {
continue
}
matchesCount := 0
for j := 0; j < patternLength; j++ {
if text[i+j] != pattern[j] {
break
}
matchesCount++
}
if matchesCount == patternLength {
return i
}
}
return -1
}
func TestRabinKarp(t *testing.T) {
random := rand.New(rand.NewSource(time.Now().UnixNano()))
letters := []rune("abcdefghijklmnopqrstuvwxyz")
text := make([]rune, random.Intn(15-10)+10)
for i := range text {
text[i] = letters[rand.Intn(len(letters))]
}
end := random.Intn(len(text)-5) + 5
start := random.Intn(end)
result := RabinKarp(string(text), string(text[start:end]))
if result == -1 {
t.Fail()
}
}
