Algoritmos de Correspondência de Cadeias de Caracteres
KMP (Knuth-Morris-Pratt)
O KMP otimiza a correspondência de padrões ao reutilizar informações de correspondências anteriores. Em vez de reiniciar a busca do início após uma falha, ele utiliza um pré-processamento para determinar o próximo ponto de comparação, reduzindo a complexidade para O(n + m).
O pré-processamento calcula o array de falha, ...
Publicado em 7-11 21:28
Exercícios de Implementação do Autômato de Sufixo
O Autômato de Sufixo (SAM) é uma estrutura de dados eficiente para manipulação de strings. A seguir, apresento soluções para diversos problemas envolvendo SAM, com código reescrito para clareza e concisão.
Contagem de Substrings Distintas
Para uma string S, o número de substrings distintas pode ser calculado pela soma das diferenças entre o com ...
Publicado em 6-12 23:03