*The insight* is that you can efficiently compute the hash value of a subsequence using the hash value of previous subsequence if you use the right hash function. A polynomial with the string characters as coefficients works well. Let <tex>H(c)=c[0]a^{n-1} + c[1]a^{n-2}+...+c[n-1]</tex> be the hash function for the string c.
All the operations are done modulo a prime number so that we don’t have to deal with large integers.

Let’s see what happens when we go from $H(S[i..i+n-1])$ to $H(S[i+1..i+n])$:

Let’s see what happens when we go from H(S[i..i+n-1]) to H(S[i+1..i+n]):

!blog/rolling-hash?image10.png!

Here's some code:
== code(c) |

  an = 1

  an = 1;

  rolling_hash = 0;

  for i in range(0, n):
    rolling_hash = (rolling_hash * a + S[i]) % MOD
    an = (an * a) % MOD
  if rolling_hash == hash_p:
    print "match"
  for i in range(1, m - n + 1):
    rolling_hash = (rolling_hash * a + S[i + n - 1] - an * S[i - 1]) % MOD
    if rolling_hash == hash_p:

  for (int i = 0; i < n; i++) {
    rolling_hash = (rolling_hash * a + S[i]) % MOD;
    an = (an * a) % MOD,
  }
 
  for (int i = 1; i <= n - m; i++)
    rolling_hash = (rolling_hash * a + S[i + n - 1] - an * S[i - 1]) % MOD,
    if (rolling_hash == hash_p)

        print "match"

  }
}

==
h2. Substrings of variable length