Algoritmo de coincidencia de patrones para cadenas
Este artículo presenta principalmente algoritmos de coincidencia de patrones de cadenas, incluidos el algoritmo BF, el algoritmo RK, el algoritmo KMP y el algoritmo BM. Se utilizan diferentes algoritmos para encontrar subcadenas de cadenas de destino. algoritmos. Proceso para mejorar la capacidad de pensamiento lógico
El propósito de la coincidencia de patrones es encontrar subcadenas en la cadena de destino que sean iguales a la cadena del patrón. Aquí, la cadena principal se llama s, la cadena patrón se llama t, la longitud de la cadena principal es n y la longitud de la cadena patrón es m
El algoritmo de fuerza bruta compara la cadena objetivo y la cadena del patrón uno por uno para cada carácter. Tiene el peor rendimiento, pero es el más utilizado porque es sencillo de implementar y consume menos rendimiento cuando la cadena es pequeña.
O(n*m)
El algoritmo RK convierte el problema de comparación de cadenas en un problema de comparación de valores hash.
Cambie la comparación de cada carácter de la cadena de patrón t para comparar la cadena en su conjunto con el valor hash de la cadena de destino, reduciendo así el número de comparaciones
Anterior, el La comparación de cadenas y subcadenas de patrones requería comparar cada carácter, pero ahora solo es necesario comparar secuencialmente el valor hash en su conjunto. Entonces esto reduce el número de comparaciones.
Algoritmo hash
Aquí podemos encontrar un problema de conflicto hash, por ejemplo, los valores hash de "abc" y "bc" son los mismos porque el bit más alto es 0 .
Algoritmo de colisión hash:
Utilice el resultado anterior para calcular el siguiente valor hash
Esto se debe a que las subcadenas adyacentes de la cadena de destino, de hecho, solo la primera y los últimos caracteres son diferentes, los demás caracteres son iguales,
por lo que podemos usar el resultado anterior para restar el valor hash. Puede utilizar el resultado del cálculo anterior, restar el primer carácter de la cadena anterior y agregar el último carácter de esta cadena, lo cual es suficiente.
Para abordar las deficiencias de BF, se pueden realizar comparaciones de saltos de varios caracteres en el algoritmo KMP para evitar retrocesos innecesarios de la cadena de destino.
Ejemplo:
Breve descripción:
Cadena de verdad:
Coincidencia:
Ejemplo: carácter de destino Cadena : "abxabcabcaby", cadena de patrón: "abcaby"
Cadena de patrón La subcadena verdadera máxima de la cadena de patrón es ab,
Al hacer coincidir, encontramos la subcadena de la cadena de destino. la cadena abcabc coincide con los primeros caracteres de la cadena del patrón, pero el último carácter no coincide
Entonces, comenzamos a hacer coincidir la cadena del patrón de abc después de la cadena de destino abcabc sin coincidir con el abc anterior.
Es decir, salta directamente del carácter a anterior al siguiente carácter a en lugar de comenzar desde el carácter b.
Habrá una situación como esta:
Idea de implementación:
Este es un algoritmo de coincidencia de cadenas muy eficiente. Hay estadísticas experimentales y su rendimiento es. Tres o cuatro veces mayor que el famoso algoritmo KMP. El algoritmo BM tiene muchos principios complejos y es difícil de entender. Es necesario utilizar más el cerebro al aprender.
La idea de implementación es básicamente la misma que la del algoritmo KMP. Primero calculan la subcadena verdadera en la cadena del módulo y luego encuentran el tamaño de la subcadena verdadera. Cuando ocurre una discrepancia, coincide directamente después de la verdadera. substring. La diferencia Para el algoritmo KMP, coincide de atrás hacia adelante
En comparación con el algoritmo KMP, aquí se agrega una regla de caracteres incorrectos, que por supuesto puede saltar más rápido que el algoritmo KMP. También puedes usar la regla del mal carácter. El algoritmo en sí también puede utilizar malas reglas de caracteres
malas reglas de caracteres
buenas reglas de sufijos