Rabin-Karp Algorithm

.encode string into integer

  a  b  d  e  a  b  c            text
  a  b  c                        pattern
                                 d = 26


[a b c]26 = 1 * 262 + 2 * 26 + 3
[a b c]26 = 1 * 262 + 2 * 26 + 4
[a b c]26 = 2 * 262 + 4 * 26 + 5 = ([a b d]26 - 1 * 262) * 26 + 5

text:       a1 a2¡K¡Kai ai+1¡Kai+M-1 ai+M¡K¡KaN
pattern:             p1 p2¡KpM

x = [ai ai+1¡Kai+M-1]
=>  [ai ai+1¡Kai+M-1] = (x - aidM-1) * d + ai+M (mod q)

T = N + M