O quê é o Algoritmo Força-Bruta?
O Algoritmo Força-Bruta consiste em uma forma simples, ingênua e ineficiente para realizar o casamento de padrões. O algoritmo funciona deslizando uma janela de comparação no texto de entrada símbolo a símbolo e comparando se cada trecho de texto considerado corresponde ao padrão buscado.
Quais são as características do Algoritmo Força-Bruta?
- O Algoritmo de Força-Bruta faz uma busca exata de um padrão em um texto de entrada.
- O Algoritmo de Força-Bruta funciona deslizando uma janela de comparação pelo texto de entrada.
- O Algoritmo de Força-Bruta não necessita de espaço auxiliar de memória para funcionar.
- O Algoritmo de Força-Bruta é ineficiente.
- O desempenho do Algoritmo Força-Bruta não depende do padrão buscado.
Qual é o Algoritmo Força-Bruta?
- Posicione a janela deslizante de comparação no primeiro símbolo do texto de entrada e inicie a busca:
- Compare o trecho de texto na janela deslizante com o padrão buscado, começado pelo último símbolo do padrão em direção ao primeiro.
- Caso algum símbolo seja diferente, avance para o próximo símbolo no texto de entrada.
- Caso o trecho de texto corresponda ao padrão buscado, adicione esse trecho ao conjunto de trechos encontrados e interrompa a busca.
- Retorne o conjunto de trechos que correspondem ao padrão buscado. Se nenhuma correspondência foi encontrada, esse conjunto está vazio.
Qual o desempenho do Algoritmo Força-Bruta?
Melhor Caso
O melhor caso para o Algoritmo Força-Bruta para o casamento de padrões ocorre quando o padrão buscado está nas posições iniciais do texto de entrada. Nesse cenário, o desempenho do algoritmo é linear no número de comparações, em função do comprimento n do padrão buscado:
Pior Caso
O pior caso para o Algoritmo Força-Bruta para o casamento de padrões ocorre quando o padrão buscado não está no texto de entrada. Nesse cenário, o desempenho do algoritmo é quadrático no número de comparações, em função do comprimento m do texto de entrada e do comprimento n do padrão buscado: