A correspondência de padrões é amplamente utilizada na ciência da computação e em muitos outros campos. Algoritmos de correspondência de padrões são usados para procurar padrões em um texto ou conjunto de dados maior. Um dos algoritmos mais populares para correspondência de padrões é o Boyer Moore algoritmo, que foi publicado pela primeira vez em 1977. Neste artigo, discutiremos algoritmos de correspondência de padrões em C e como eles funcionam.
O que é um algoritmo de correspondência de padrões?
Algoritmos de correspondência de padrões são usados para encontrar padrões em um conjunto maior de dados ou texto. Esses algoritmos funcionam comparando um padrão com um conjunto de dados ou texto maior e determinando se o padrão está presente ou não. Os algoritmos de correspondência de padrões são importantes porque nos permitem pesquisar rapidamente padrões em grandes conjuntos de dados.
centralizando uma imagem em css
Algoritmo de correspondência de padrões de força bruta:
A correspondência de padrões de força bruta é o algoritmo de correspondência de padrões mais simples. Envolve comparar os caracteres do padrão com os caracteres do texto, um por um. Se todos os caracteres corresponderem, o algoritmo retornará a posição inicial do padrão no texto. Caso contrário, o algoritmo passa para a próxima posição no texto e repete a comparação até que uma correspondência seja encontrada ou o final do texto seja alcançado. A complexidade temporal do algoritmo de força bruta é O(MXN) , onde M denota o comprimento do texto e N denota o comprimento do padrão.
Algoritmo de correspondência de padrões ingênuo:
O algoritmo Naive Pattern Matching é uma melhoria em relação ao algoritmo de Força Bruta. Evita comparações desnecessárias ao pular algumas posições do texto. O algoritmo começa a comparar o padrão com o texto na primeira posição. Se os caracteres corresponderem, passa para a próxima posição e repete a comparação. Se os caracteres não corresponderem, o algoritmo passa para a próxima posição no texto e compara o padrão com o texto novamente. A complexidade de tempo do algoritmo Naive também é O(MXN) , mas é mais rápido que o algoritmo de força bruta na maioria dos casos.
Algoritmo Knuth-Morris-Pratt:
O Knuth-Morris-Pratt (KMP) algoritmo é um algoritmo de correspondência de padrões mais avançado. Baseia-se na observação de que quando ocorre uma incompatibilidade, algumas informações sobre o texto e o padrão podem ser utilizadas para evitar comparações desnecessárias. O algoritmo pré-calcula uma tabela que contém informações sobre o padrão. A tabela determina quantos caracteres do padrão podem ser ignorados quando ocorre uma incompatibilidade. A Complexidade Temporal do KMP algoritmo é SO(M+N) .
O Algoritmo Boyer-Moore:
Um dos algoritmos de correspondência de padrões mais populares é o Boyer Moore algoritmo. Este algoritmo foi publicado pela primeira vez em 1977 por Robert S. Boyer e J Strother Moore. O Boyer Moore O algoritmo compara um padrão com um conjunto maior de dados ou texto da direita para a esquerda, em vez da esquerda para a direita, como acontece com a maioria dos outros algoritmos de correspondência de padrões.
O Boyer Moore O algoritmo tem dois componentes principais: a regra do mau caráter e a regra do sufixo bom. A regra de caracteres inválidos funciona comparando o caractere no padrão com o caractere correspondente nos dados ou texto. Se os caracteres não corresponderem, o algoritmo moverá o padrão para a direita até encontrar um caractere que corresponda. A boa regra do sufixo compara o sufixo do padrão com o sufixo correspondente dos dados ou texto. Se os sufixos não corresponderem, o algoritmo moverá o padrão para a direita até encontrar um sufixo correspondente.
O Boyer Moore O algoritmo é conhecido por sua eficiência e é amplamente utilizado em muitas aplicações. É considerado um dos algoritmos de correspondência de padrões mais rápidos disponíveis.
Implementando o algoritmo Boyer-Moore em C:
Para implementar o Boyer Moore algoritmo em C, podemos começar definindo a regra do mau caráter. Podemos usar um array para armazenar a última ocorrência de cada caractere no padrão. Esta matriz pode determinar até que ponto devemos mover o padrão para a direita quando ocorre uma incompatibilidade.
Aqui está um exemplo de como podemos implementar a regra do mau caráter em C:
c++ converte int em string
Código C:
void bad_character_rule(char *pattern, int pattern_length, int *bad_char) { int i; for (i = 0; i <no_of_chars; i++) bad_char[i]="-1;" for (i="0;" i < pattern_length; bad_char[(int) pattern[i]]="i;" } pre> <p>In this example, we first initialize the array to -1 for all characters. We then iterate through the pattern and update the array with the last occurrence of each character in the pattern.</p> <p>Next, we can implement the good suffix rule. We can use an array to store the length of the longest suffix of the pattern that matches a suffix of the data or text. This array can be used to determine how far we need to move the pattern to the right.</p> <hr></no_of_chars;>