Função de Prefixo do KMP
Encontre um padrão em O(n + m).
Função de Prefixo do KMP é uma aula grátis de Coding Interview Prep no CoddyKit. Esta é a aula 1 de 4. Você pode ler a aula completa abaixo gratuitamente — depois pratica ao vivo no navegador com um editor de código integrado e um tutor de IA 24/7. Faz parte do caminho de aprendizado de Coding Interview Prep, e seu progresso é sincronizado entre a web e o app CoddyKit. O curso de Coding Interview Prep inclui 4 aulas no total.
O problema de encontrar padrões
Você quer encontrar onde um padrão aparece dentro de um texto grande. As verificações ingênuas são lentas, por isso as competições valorizam uma varredura mais inteligente. 🔍
Por que a busca ingênua é custosa
Comparar o padrão em cada posição pode custar O(n*m) de tempo. Em entradas grandes, isso estoura silenciosamente seu limite de tempo.
Conheça a função de prefixo
A função de prefixo mede, em cada posição, o maior prefixo próprio que também é um sufixo. Ela é o coração do KMP.
Prefixo e sufixo próprios
Um prefixo ou sufixo próprio não inclui a cadeia inteira. Para ababa, o maior par correspondente tem comprimento 3: aba.
O que pi[i] armazena
Armazenamos os valores em um vetor chamado pi. Aqui, pi[i] é o comprimento do maior par prefixo-sufixo para a fatia que termina no índice i.
Construindo pi em uma passagem
Você constrói pi da esquerda para a direita, reutilizando valores anteriores em vez de verificar tudo novamente. Essa reutilização é o truque principal.
def prefix_function(s):
pi = [0] * len(s)
return piO laço de retorno
Quando os caracteres não coincidem, volte para pi[k-1] em vez de redefinir para zero. Isso evita refazer trabalho.
while k > 0 and s[i] != s[k]:
k = pi[k - 1]Estendendo uma correspondência
Se os caracteres atuais coincidirem, aumente o comprimento em um e registre-o. Incompatibilidades quando o comprimento é zero simplesmente continuam em zero.
if s[i] == s[k]:
k += 1
pi[i] = kBuscando com o truque
Para buscar um padrão em um texto, una-os como pattern + sep + text. Qualquer valor de pi igual ao comprimento do padrão indica uma correspondência completa.
combined = pattern + chr(0) + text
pi = prefix_function(combined)Por que um separador é importante
O separador é um símbolo que não aparece em nenhuma das duas cadeias. Ele impede que correspondências atravessem a junção e produzam falsos resultados.
A vantagem do tempo linear
Tanto a construção quanto a busca executam em O(n + m). Cada caractere é processado uma vez, então o KMP funciona bem com entradas enormes de competições.
Verificação rápida
Avalie seu entendimento do que a função de prefixo registra.
Recapitulação: KMP em resumo
Você aprendeu a função de prefixo: construa pi uma vez, retorne em caso de incompatibilidades e faça a busca em tempo linear. Isso é o KMP em resumo. 🎯
Perguntas Frequentes
A aula “Função de Prefixo do KMP” é grátis?
Sim — o texto completo de “Função de Prefixo do KMP” é grátis para ler aqui na web. Para praticá-la interativamente (um editor de código integrado e um tutor de IA 24/7) e desbloquear o restante do curso de Coding Interview Prep, atualize para CoddyKit PRO. O curso de Coding Interview Prep inclui 4 aulas no total.
O que vou aprender em “Função de Prefixo do KMP”?
Encontre um padrão em O(n + m). Você pratica Coding Interview Prep com código prático que executa diretamente no navegador, e um tutor de IA 24/7 responde suas dúvidas enquanto trabalha na aula.
Preciso ter experiência prévia para começar Coding Interview Prep?
Nenhuma experiência prévia é necessária. Coding Interview Prep no CoddyKit é estruturado para alunos iniciantes até avançados, então você pode começar aqui ou desde o início e aprender no seu ritmo. Esta é a aula 1 de 4.
Quanto tempo leva a aula “Função de Prefixo do KMP”?
A maioria das aulas CoddyKit leva cerca de 5–10 minutos. Cada uma é compacta e interativa, então você faz progresso constante e retoma exatamente de onde parou entre web e app.
Posso escrever e executar código nesta aula de Coding Interview Prep?
Sim. Cada aula de Coding Interview Prep inclui um editor de código integrado, então você escreve e executa código real direto no navegador e recebe feedback de IA instantaneamente — nenhuma configuração local necessária.
Todas as aulas deste curso
- Função de Prefixo do KMP
- Hashing Polinomial de Strings
- Função Z para Busca de Padrões
- Tries para Consultas por Prefixo