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