Questão de Algoritmos e Estrutura de Dados — Algoritmos — IBFC 2023
Algoritmos e Estrutura de Dados›Algoritmos
Código
qq930983
Banca
IBFC
Órgão
CET-Santos
Ano
2023
Nível
Superior
Cargo
Analista de Gestão - TI
Você faz parte de uma equipe de desenvolvimento, onde existem pessoas que trabalham em várias partes do sistema. À você foi atribuída a tarefa de preparar uma função de descoberta de uma substring no portal onde o sistema será acessado. Para tanto você foi pesquisar alguns algoritmos que poderiam ser usados, e encontrou o algoritmo de:
AKnuth-Morris-Pratt
BRivest-Shamir-Adleman
CDijkstra-Mennon
DLennin-Sherpmann
Revelar gabarito e comentário▾
GabaritoA — Knuth-Morris-Pratt
Comentário gerado por IA. É um apoio ao estudo, ancorado em fontes, mas pode conter imprecisões — confira sempre na fonte oficial (lei, súmula, edital e gabarito da banca). Encontrou um erro? Use “Reportar”.
Algoritmos de busca de substring
Gabarito: letra A. O algoritmo de Knuth-Morris-Pratt (KMP) é um clássico para busca eficiente de padrões (substrings) em textos, com complexidade O(n+m). É o único listado que se aplica diretamente à tarefa de descoberta de substring.
Algoritmos de busca de substring: KMP (Knuth-Morris-Pratt) (Busca eficiente de padrões, Complexidade O(n+m), Tabela de prefixo evita retrocesso); RSA (Rivest-Shamir-Adleman) (Criptografia assimétrica, Não é busca de substring); Dijkstra-Mennon (Algoritmo fictício, Não existe na computação); Lennin-Sherpmann (Algoritmo fictício, Não é método real)
Alternativa A — ✅ Correta ⟵ GABARITO
O Knuth-Morris-Pratt é o algoritmo correto. Ele utiliza uma tabela de prefixo para evitar retrocesso no texto, tornando a busca linear. É ideal para encontrar ocorrências de uma substring em um texto, exatamente a tarefa descrita no enunciado.
Alternativa B — ❌ Incorreta
Rivest-Shamir-Adleman (RSA) é um algoritmo de criptografia assimétrica, utilizado para segurança e troca de chaves, não para busca de substrings. A banca tentou confundir com um algoritmo famoso, mas de área completamente diferente.
Alternativa C — ❌ Incorreta
Dijkstra-Mennon não é um algoritmo real. Edsger Dijkstra desenvolveu algoritmos para caminhos mínimos (Dijkstra), mas não há um algoritmo de busca de substring com esse nome. A banca misturou nomes de forma fictícia.
Alternativa D — ❌ Incorreta
Lennin-Sherpmann não é um algoritmo conhecido na computação. Não corresponde a nenhum método real de busca de substring, sendo um distrator inventado.