# Rabin-Karp Algorithm

# Intro

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]`

…

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 .

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