Algoritmo KMP: Função de Prefixo e Busca de Padrões em C++
Nota: todos os índices utilizados neste artigo são baseados em zero.
Prefixos e sufixos
Dado uma string s, um prefixo é qualquer substring que inicia na primeira posição de s. O prefixo que termina na posição i é denotado por s[0..i]. Um prefixo próprio é todo prefixo de s diferente dela mesma.
De forma análoga, um sufixo é uma substring que te ...
Publicado em 9-15 00:24
Entendendo o Algoritmo Knuth-Morris-Pratt (KMP)
O algoritmo Knuth-Morris-Pratt, ou KMP, é um dos métodos mais eficientes para busca de padrões em strings. Diferente da abordagem de força bruta (Brute Force), que reinicia a comparação do zero a cada falha, o KMP utiliza o conhecimento adquirido em comparações parciais anteriores para evitar verificações redundantes.
O Conceito de Prefixos e S ...
Publicado em 7-28 19:00