La coincidencia de patrones se utiliza ampliamente en informática y muchos otros campos. Los algoritmos de coincidencia de patrones se utilizan para buscar patrones dentro de un conjunto de datos o texto más grande. Uno de los algoritmos más populares para la coincidencia de patrones es el boyer-moore algoritmo, que se publicó por primera vez en 1977. En este artículo, analizaremos los algoritmos de coincidencia de patrones en C y cómo funcionan.
¿Qué es un algoritmo de coincidencia de patrones?
Los algoritmos de coincidencia de patrones se utilizan para encontrar patrones dentro de un conjunto más grande de datos o texto. Estos algoritmos funcionan comparando un patrón con un conjunto de datos o texto más grande y determinando si el patrón está presente o no. Los algoritmos de coincidencia de patrones son importantes porque nos permiten buscar patrones en grandes conjuntos de datos rápidamente.
ajuste de cadena java
Algoritmo de coincidencia de patrones de fuerza bruta:
La coincidencia de patrones de fuerza bruta es el algoritmo de coincidencia de patrones más simple. Implica comparar los caracteres del patrón con los caracteres del texto uno por uno. Si todos los caracteres coinciden, el algoritmo devuelve la posición inicial del patrón en el texto. De lo contrario, el algoritmo pasa a la siguiente posición del texto y repite la comparación hasta encontrar una coincidencia o llegar al final del texto. La complejidad temporal del algoritmo de fuerza bruta es O(MXN) , dónde METRO denota la longitud del texto y norte denota la longitud del patrón.
Algoritmo ingenuo de coincidencia de patrones:
El algoritmo Naive Pattern Matching es una mejora con respecto al algoritmo Brute Force. Evita comparaciones innecesarias al saltarse algunas posiciones en el texto. El algoritmo comienza a comparar el patrón con el texto en la primera posición. Si los caracteres coinciden, pasa a la siguiente posición y repite la comparación. Si los caracteres no coinciden, el algoritmo pasa a la siguiente posición en el texto y compara el patrón con el texto nuevamente. La complejidad temporal del algoritmo Naive también es O(MXN) , pero es más rápido que el algoritmo de Fuerza Bruta en la mayoría de los casos.
Algoritmo de Knuth-Morris-Pratt:
El Knuth-Morris-Pratt (KMP) El algoritmo es un algoritmo de coincidencia de patrones más avanzado. Se basa en la observación de que cuando ocurre una discrepancia, se puede utilizar cierta información sobre el texto y el patrón para evitar comparaciones innecesarias. El algoritmo precalcula una tabla que contiene información sobre el patrón. La tabla determina cuántos caracteres del patrón se pueden omitir cuando se produce una discrepancia. La complejidad temporal de la KMP el algoritmo es O(M+N) .
El algoritmo de Boyer-Moore:
Uno de los algoritmos de coincidencia de patrones más populares es el boyer-moore algoritmo. Este algoritmo fue publicado por primera vez en 1977 por Robert S. Boyer y J Strother Moore. El boyer-moore El algoritmo compara un patrón con un conjunto más grande de datos o texto de derecha a izquierda en lugar de de izquierda a derecha, como ocurre con la mayoría de los otros algoritmos de coincidencia de patrones.
El boyer-moore El algoritmo tiene dos componentes principales: la regla del mal carácter y la regla del sufijo bueno. La regla del carácter incorrecto funciona comparando el carácter del patrón con el carácter correspondiente en los datos o el texto. Si los caracteres no coinciden, el algoritmo mueve el patrón hacia la derecha hasta encontrar un carácter que coincida. La buena regla del sufijo compara el sufijo del patrón con el sufijo correspondiente de los datos o texto. Si los sufijos no coinciden, el algoritmo mueve el patrón hacia la derecha hasta encontrar un sufijo coincidente.
El boyer-moore El algoritmo es conocido por su eficiencia y se usa ampliamente en muchas aplicaciones. Se considera uno de los algoritmos de coincidencia de patrones más rápidos disponibles.
Implementando el algoritmo Boyer-Moore en C:
Para implementar el boyer-moore algoritmo en C, podemos comenzar definiendo la regla del carácter malo. Podemos usar una matriz para almacenar la última aparición de cada carácter en el patrón. Esta matriz puede determinar cuánto debemos mover el patrón hacia la derecha cuando ocurre una discrepancia.
Aquí hay un ejemplo de cómo podemos implementar la regla de los malos caracteres en C:
ejemplos de máquina de Moore
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;>