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ínimo de comparações. Determine esse mínimo em função de
e
.
Passo 1
Resumo do enunciado: a gente tem duas cadeias,
de tamanho
e
de tamanho
, e o algoritmo de força bruta de casamento de cadeias faz comparações de letra por letra para achar ocorrências de
em
. O que a questão pede é: dê um exemplo concreto de
e
que faça o algoritmo usar o menor número possível de comparações e, em seguida, determine esse mínimo em função de
e
.
Matéria: algoritmo de string matching (força bruta). Vamos precisar entender como ele “varre” o texto e conta comparações até achar um mismatch.
Matéria: algoritmo de string matching (força bruta). Vamos precisar entender como ele “varre” o texto e conta comparações até achar um mismatch.
Passo 2
Como o algoritmo de força bruta funciona?
- Ele tenta encaixar todo o padrão
em cada posição de , da primeira até a posição . - Em cada alinhamento, ele compara as letras de
com as letras correspondentes de , da esquerda pra direita, e para no primeiro mismacth (ou termina quando casou todas). - Cada comparação conta 1. Então, se bater o primeiro caractere a cada deslocamento e já der mismatch, ele faz só 1 comparação naquele alinhamento.
Passo 3
Pra minimizar o número total de comparações, queremos que em cada um dos
deslocamentos o algoritmo falhe logo na primeira comparação. Assim:
- Número de alinhamentos =
. - Em cada alinhamento, só 1 comparação (mismatch na letra 1).
Total de comparações =.
Passo 4
Exemplo prático:
- Seja
(uma sequência de letras ‘a’). - Seja
(uma sequência de letras ‘b’).
Em cada posição que a gente encaixeem , a primeira comparação é ‘a’ vs. ‘b’ → já dá mismatch. Então pra cada um dos deslocamentos, só 1 comparação é feita.
Resposta
O número mínimo de comparações é