When I was reading the go standard library, I found string.Index (which returns the first index of occursion of string s in string t) used Rabin-Karp algorithm. So I implemented the one.

Straight Forward Algorithm

When you try to find string s in string t, a simple way is to compare s with t[0:len(s)], t[1:len(s)+1]

for i := 0; i <= len(t)-len(s); i++ {
	if s == t[i : i+len(s)] {
		return i
return -1

The problem is this algorithm is O(|s||t|). The wasteful part is comparing s with t[i:i+len(s)] every time in the loop. Which lead us to Rabin-Karp algorithm.

Rabin-Karp Algorithm

The only difference and the key idea of Rabin-Karp algorithm is comparing two strings using rolling hash value of them. Rolling hash skip computation by re-uses previous hash value. The following is the definition of it.

where is a random prime and is the length of . It is a simple polynomial, thus it is easy to calculate from .

for i := 1; i < lt-ls+1; i++ {
	ht -= int(t[i-1]) * pow(prime, len(s)-1) // remove the first character
	ht = ht*prime + int(t[i+len(s)-1])       // append the next character
	if hs == ht && s == t[i:i+len(ls)] {
		return i

The source code is available at gist. Thanks for reading, happy hacking!


9. Table Doubling, Karp-Rabin