La concordança de patrons s'utilitza àmpliament en informàtica i molts altres camps. Els algorismes de concordança de patrons s'utilitzen per cercar patrons dins d'un text o conjunt de dades més gran. Un dels algorismes més populars per a la concordança de patrons és el Boyer-Moore algorisme, que es va publicar per primera vegada el 1977. En aquest article, parlarem dels algorismes de concordança de patrons en C i com funcionen.
Què és un algorisme de concordança de patrons?
Els algorismes de concordança de patrons s'utilitzen per trobar patrons dins d'un conjunt més gran de dades o text. Aquests algorismes funcionen comparant un patró amb un conjunt de dades o text més gran i determinant si el patró està present o no. Els algorismes de concordança de patrons són importants perquè ens permeten cercar patrons en grans conjunts de dades ràpidament.
llista de creació de java
Algoritme de concordança de patró de força bruta:
La concordança de patrons de força bruta és l'algoritme de concordança de patrons més senzill. Consisteix en comparar els caràcters del patró amb els caràcters del text un per un. Si tots els caràcters coincideixen, l'algoritme retorna la posició inicial del patró al text. Si no, l'algoritme es mou a la següent posició del text i repeteix la comparació fins que es trobi una coincidència o s'arribi al final del text. La complexitat temporal de l'algoritme de força bruta és O(MXN) , on M indica la longitud del text i N indica la longitud del patró.
Algoritme de concordança de patró ingenu:
L'algoritme Naive Pattern Matching és una millora respecte a l'algoritme Brute Force. Evita comparacions innecessàries saltant algunes posicions del text. L'algorisme comença a comparar el patró amb el text a la primera posició. Si els personatges coincideixen, es mou a la següent posició i repeteix la comparació. Si els caràcters no coincideixen, l'algoritme es mou a la següent posició del text i torna a comparar el patró amb el text. La complexitat temporal de l'algoritme Naive també ho és O(MXN) , però és més ràpid que l'algorisme de força bruta en la majoria dels casos.
Algoritme Knuth-Morris-Pratt:
El Knuth-Morris-Pratt (KMP) L'algoritme és un algorisme de concordança de patrons més avançat. Es basa en l'observació que quan es produeix un desajust, es pot utilitzar alguna informació sobre el text i el patró per evitar comparacions innecessàries. L'algorisme calcula prèviament una taula que conté informació sobre el patró. La taula determina quants caràcters del patró es poden saltar quan es produeix un desajust. La complexitat temporal del KMP algorisme és O(M+N) .
L'algoritme de Boyer-Moore:
Un dels algorismes de concordança de patrons més populars és el Boyer-Moore algorisme. Aquest algorisme va ser publicat per primera vegada l'any 1977 per Robert S. Boyer i J Strother Moore. El Boyer-Moore L'algoritme compara un patró amb un conjunt més gran de dades o text de dreta a esquerra en lloc d'esquerra a dreta, com passa amb la majoria dels altres algorismes de concordança de patrons.
El Boyer-Moore L'algorisme té dos components principals: la regla de caràcters dolents i la regla de bons sufixos. La regla del caràcter dolent funciona comparant el caràcter del patró amb el caràcter corresponent de les dades o del text. Si els caràcters no coincideixen, l'algoritme mou el patró cap a la dreta fins que trobi un caràcter que coincideixi. La regla de bon sufix compara el sufix del patró amb el sufix corresponent de les dades o del text. Si els sufixos no coincideixen, l'algoritme mou el patró cap a la dreta fins que trobi un sufix que coincideixi.
El Boyer-Moore L'algorisme és conegut per la seva eficiència i s'utilitza àmpliament en moltes aplicacions. Es considera un dels algorismes de concordança de patrons més ràpids disponibles.
Implementació de l'algorisme de Boyer-Moore en C:
Per implementar el Boyer-Moore algorisme en C, podem començar definint la regla de caràcter dolent. Podem utilitzar una matriu per emmagatzemar l'última ocurrència de cada caràcter del patró. Aquesta matriu pot determinar fins a quin punt hem de moure el patró cap a la dreta quan es produeix un desajust.
Aquí teniu un exemple de com podem implementar la regla de caràcter dolent a C:
primer ordinador portàtil
Codi 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;>