# 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 $p$ is a random prime and $k$ is the length of $s$. It is a simple polynomial, thus it is easy to calculate $h_{i+1}$ from $h_i$.

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

# References

9. Table Doubling, Karp-Rabin