Karp Rabin

A ideia básica é associar cada palavra num alfabeto de tamanho m a um valor numa tabela hash. Se o conteúdo W = T[i:i+m-1] da janela na posição i é tal que φ(W) != φ(P), então W não é ocorrência de P. Se φ(W) == φ(P), precisamos verificar se W == P.

Algoritmo Karp-Rabin
Entrada: T = t1, ..., tn; P = p1, ..., pn;
Saída: E(P, T) // ocorrências do padrão P no texto T
início
  f <- φ(P)
  w <- φ(T[:m])
  para i <- 1, ..., n - m + 1 faça
    se f = w então
      se T[i:i+m-1] = P então
        E <- E U {i}
      fim-se
    fim-se
    w <- φ(T[i+1:i+m])
  fim-faça
  retorna E
fim

A fim de melhorar o desempenho do algoritmo, é importante fazer uma boa escolha para a função de hash φ. Uma abordagem viável é considerar palavras no alfabeto Σ como números base s = |Σ| módulo r, em que r indica o tamanho da tabela hash, e implementar uma rolling hash.

Algoritmo Karp-Rabin Estendido
Entrada: T, P
Saída: E(P, T)
início
  p <- S^(m-1) mod r
  //TODO