Back>
Instead of comparing string literally, we can compare 2 strings' hashCode. There is a tiny chance that 2 strings with the same hashCode but different characters, but we can double check.
The only barrier for this approach is to calculate hashCode cheap.
Rabin and Karp found one cheap hash function, thus practically find the needle in the haystack with 7N time cost and O(1) space cost to find the needle in a haystack. Since what is compared is the hashCode, the worst case performance is also 7N. The algorithm don't have backup in place, it is good for process stream of String.
RabinKarp.java
