Dê exemplos de cadeias
e
de comprimentos
e
, respectivamente, tais que o algoritmo de força bruta para o casamento de cadeias efetue um número máximo de comparações. Determine esse máximo em função de
e
.
Passo 1
Beleza, temos um exercício de casamento de cadeias (busca de padrão em texto) usando o método de força bruta.
Enunciado: Dadas duas cadeias X (texto) de tamanho e Y (padrão) de tamanho
, queremos encontrar exemplos de X e Y que façam o algoritmo ingênuo gastar o máximo possível de comparações, e depois expressar esse número máximo em função de
e
.
Conteúdo: algoritmo ingênuo de string matching, análise de pior caso.
O que vamos precisar: entender como o algoritmo compara caractere a caractere em cada deslocamento e contar quantas comparações ele faz.
Enunciado: Dadas duas cadeias X (texto) de tamanho
Conteúdo: algoritmo ingênuo de string matching, análise de pior caso.
O que vamos precisar: entender como o algoritmo compara caractere a caractere em cada deslocamento e contar quantas comparações ele faz.
Passo 2
Como funciona o algoritmo de força bruta (ingênuo)?
- Para cada deslocamento
de até , a gente alinha o padrão Y em X começando na posição do texto. - Compara
com , depois com , e assim por diante, até ou bater todos os caracteres (achando ocorrência) ou dar um mismatch e parar naquele deslocamento.
No pior caso, a gente quer que o algoritmo gaste o maior número de comparações possível em CADA alinhamento, e que tente todos os alinhamentos de
a
.
Passo 3
Para maximizar comparações em cada alinhamento, façamos com que ele acerte nos primeiros
caracteres e só erre no
-ésimo.
Uma escolha clássica:
Uma escolha clássica:
- Texto
(ou seja, ) - Padrão
(ou seja, )
Então, em cada deslocamento
, o algoritmo compara:
e aí, no último,
— dá mismatch só no final, forçando exatamente
comparações naquele deslocamento.
Passo 4
Quantos deslocamentos temos? De
até
, ou seja,
tentativas.
Em cada tentativa o custo é de comparações.
Logo, o total de comparações no pior caso é
Em cada tentativa o custo é de
Logo, o total de comparações no pior caso é
Resposta
Exemplos que forçam o pior caso:
X = e Y =
.
Máximo de comparações do algoritmo de força bruta:
X =
Máximo de comparações do algoritmo de força bruta: