Considere as cadeias X e Y com os respectivos caracteres xi ...

Alternativa Correta: A - Força Bruta

Vamos explorar o tema abordado pela questão para entender por que a alternativa correta é "Força Bruta". Este algoritmo é um método simples e direto para verificar se uma cadeia Y é uma subcadeia de X. O processo envolve tentar casar a subcadeia em cada posição possível da cadeia X até encontrar uma correspondência ou concluir que não há correspondência.

No algoritmo apresentado, é evidente que ele realiza uma verificação sequencial de cada posição possível em X para tentar encontrar a subcadeia Y. Isso caracteriza o método de Força Bruta, onde o algoritmo testa todas as possibilidades até encontrar uma solução ou esgotar as opções.

Justificativa das Alternativas Incorretas:

B - Knuth, Morris e Pratt (KMP): Este algoritmo é mais eficiente que o de força bruta, pois ele utiliza informações sobre o próprio padrão para evitar reavaliações desnecessárias, reduzindo o número de comparações. O algoritmo dado na questão, por sua vez, não utiliza tal técnica de otimização.

C - Frequência de Caracteres: Este conceito geralmente se refere ao cálculo da frequência de cada caractere em uma cadeia, e não à busca de subcadeias específicas.

D - Huffman: Este é um algoritmo usado para compressão de dados, que cria árvores de prefixo para otimizar a representação de caracteres, e não para busca de subcadeias.

E - Árvore binária: Estruturas de dados como árvores binárias são usadas para armazenar dados em uma forma hierárquica e não são diretamente aplicáveis à busca de subcadeias.

Portanto, o algoritmo ilustrado na questão corresponde ao método de Força Bruta, devido à sua abordagem de tentativa e erro para encontrar a subcadeia em questão.

Gostou do comentário? Deixe sua avaliação aqui embaixo!

FORÇA BRUTA

SZWARCFITER, Jayme L.; MARKENZON, Lilian. Estruturas de Dados e seus Algoritmos. 3.ed. [S.l.]: LTC,2010.

Pág 272

para / := 0,..., n-m faça    

i := 1    

 teste := V    

 enquanto i ≤ m e teste faça       

 se x[ l + i ] = y[ i ] então        

 i := i + 1       

 senão teste := F    

 se teste então         

 "casamento na posição I + 1 ”      

 Pare “ não há casamento "

 1) identar o algortimo é a melhor forma de visualizar o problema.

 2) o Algoritmo de força bruta testa todos os pontos e verifica se há o casamento.

Gabarito A