Sometimes you face a string processing problem for which you have the correct idea, but implementing it might not be so easy. In some of these cases, you can find a much easier to implement algorithm using hashing. These algorithms don't always give correct answer, but their probability of giving wrong answer is very low.

The simplest example is string matching, where you have to find a string inside another string. Well, you can use the KMP algorithm, which is fast enough, and easy to implement if you have enough practice. There's an alternative using hashing: Rabin-Karp algorithm. You probably should know it so you can invent more powerful algorithms for more difficult problems.

What you're looking for with strings is most likely polynomial hashing. If you have a string (in which we could represent the characters as numbers a[i] from the range [1,x]), its prefix of i characters has the hash

A[i]=sum(j=1..i)(a[i]*p^i)%M

where p and M are suitably selected primes (I use p close to max. string length, M as large as allowed — for strings of letters with length up to 1000000 p is the first prime below 1000000 and M is 1000000009.)

Another nice characteristic of this hash is that it works like prefix sums with precomputation of power of p.

You can read this site Here. It's well written .