== code(c) |
  an = 1

  rolling_hash = 0

  rolling_hash = 0;

  for i in range(0, n):
    rolling_hash = (rolling_hash * a + S[i]) % MOD
    an = (an * a) % MOD

h2. Longest common substring

bq. Given two strings A and B, compute their longest common substring.

bq. Given three strings, compute their longest common substring.

Let's solve a simpler problem: Given two strings A and B, and a number X find if they have a common sequence of length X. We use the rolling hash technique to find the hash codes for all X length substrings of A and B. Then we check if there is any common hash code between the two sets, this means A and B share a sequence of length X. We then use binary search to find the largest X.

We can find a common subsequence of fixed length in linear time using the rolling hash technique. Basically we hash all fixed length subseqences of the three strings and check if the intersection of the three respective hash sets is not empty. Now to find the largest length we can use a binary search algorithm.

The complexity of this algorithm is O(n log n).
h2. rsync