O que é o algoritmo Rabin-Karp?

O algoritmo Rabin-Karp é um algoritmo de correspondência de padrões de string que pesquisa com eficiência ocorrências de um padrão em um texto maior. Foi desenvolvido por Michael O. Rabin e Richard M. Karp em 1987.

O algoritmo utiliza uma técnica de hash para comparar os valores de hash do padrão e substrings do texto. Funciona da seguinte maneira:

• Calcule o valor hash do padrão e da primeira janela do texto.

• Deslize o padrão sobre o texto, uma posição de cada vez, e compare os valores de hash.

• Se os valores de hash corresponderem, compare os caracteres do padrão e a janela atual do texto para confirmar a correspondência.

• Se houver uma correspondência, registre a posição/índice da correspondência.

• Calcule o valor hash para a próxima janela do texto usando uma função hash contínua.

• Repita os passos 3 a 5 até que todas as posições do texto tenham sido verificadas.

A função hash contínua atualiza com eficiência o valor hash para cada nova janela, subtraindo a contribuição do primeiro caractere na janela anterior e adicionando a contribuição do próximo caractere na nova janela. Isso ajuda a evitar o recálculo do valor hash do zero para cada janela, tornando o algoritmo mais eficiente.

Programa PHP para algoritmo Rabin-Karp para pesquisa de padrões

";
      }

      // Calculate the hash value for the next window of text
      if ($i 

Saída

Pattern found at index 1 
Pattern found at index 4
Pattern found at index 7
Pattern found at index 10
Pattern found at index 13

Explicação do código

O código PHP implementa o algoritmo Rabin-Karp para pesquisa de padrões. Ele pega um padrão e um texto como entradas e procura ocorrências do padrão no texto. O algoritmo calcula os valores hash para o padrão e a primeira janela do texto. Em seguida, ele desliza o padrão sobre o texto, comparando os valores de hash da janela atual e do padrão. Se os valores de hash corresponderem, ele verifica ainda mais os caracteres um por um. Se uma correspondência for encontrada, ele imprime o índice onde o padrão foi encontrado. O algoritmo usa uma função hash contínua para atualizar com eficiência o valor hash de cada janela. O código demonstra a utilização do algoritmo procurando o padrão “BC” no texto “ABCABCABCABCABCABC”.

Conclusão

Concluindo, o programa PHP implementa efetivamente o algoritmo Rabin-Karp para pesquisa de padrões. Ao utilizar uma função hash contínua e comparar valores hash, o algoritmo procura com eficiência ocorrências de um padrão em um texto maior. O programa identifica corretamente os índices onde o padrão é encontrado no texto e gera os resultados. Com uma estrutura clara e cálculos de hash apropriados, o programa demonstra a funcionalidade e a utilidade do algoritmo Rabin-Karp para busca de padrões em PHP.