Dê exemplos de cadeias X e Y de comprimentos n e m, 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 n e m.

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.

Passo 2

Como o algoritmo de força bruta funciona?
  1. Ele tenta encaixar todo o padrão em cada posição de , da primeira até a posição .
  2. 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).
  3. 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 encaixe em , 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 é
boxedn - m + 1

Exercícios relacionados