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áximo de comparações. Determine esse máximo em função de n e m.

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 n e Y (padrão) de tamanho m, 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 n e m.
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)?
  1. Para cada deslocamento i de 0 até n-m, a gente alinha o padrão Y em X começando na posição i+1 do texto.
  2. Compara Y[1] com X[i+1], depois Y[2] com X[i+2], e assim por diante, até ou bater todos os m 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 0 a n-m.

Passo 3

Para maximizar comparações em cada alinhamento, façamos com que ele acerte nos primeiros m-1 caracteres e só erre no m-ésimo.
Uma escolha clássica:
  • Texto X = ``aaaacdots a'' (ou seja, a^n)
  • Padrão Y = ``aaacdots ab'' (ou seja, a^m-1b)
Então, em cada deslocamento i, o algoritmo compara:
Y[1]=a = X[i+1]=a,;Y[2]=a = X[i+2]=a,;dots,;Y[m-1]=a = X[i+m-1]=a
e aí, no último,
Y[m]=b = X[i+m]=a
— dá mismatch só no final, forçando exatamente m comparações naquele deslocamento.

Passo 4

Quantos deslocamentos temos? De i=0 até i=n-m, ou seja, (n-m+1) tentativas.
Em cada tentativa o custo é de m comparações.
Logo, o total de comparações no pior caso é
(n-m+1)times m

Resposta

Exemplos que forçam o pior caso:
X = a^n e Y = a^m-1b.
Máximo de comparações do algoritmo de força bruta:
m,(n - m + 1)

Exercícios relacionados