Coincidencia de patrones de cadena y estructura de datos

La coincidencia de patrones de cadenas es una operación de posicionamiento de subcadenas. Dadas dos cadenas s="s0 s1 ... s(n-1)" y t="t0 t1 ... t(m-1)" (donde n y m son las longitudes de las cadenas s y t respectivamente), El proceso de encontrar la subcadena t en la cadena principal s se llama coincidencia de patrones y t se llama patrón. Si se encuentra una subcadena igual a t en s, se dice que la coincidencia es exitosa y se devuelve la posición del subíndice de la primera aparición de t en s; de lo contrario, la coincidencia falla y se devuelve -1;

Este artículo presenta tres algoritmos de coincidencia de patrones de cadenas, a saber, el algoritmo de retroceso simple (fuerza bruta, algoritmo BF), el algoritmo KMP y las mejoras del algoritmo KMP.

A partir del carácter 0 de la cadena principal s, comience la comparación carácter por carácter con el carácter 0 de la cadena de patrón t. Si no son iguales, regrese al carácter 0 de la. cadena de patrón t y el carácter 0 de la cadena principal s 1 carácter, reinicie la comparación. Por analogía, hasta que todos los caracteres de t coincidan, la coincidencia es exitosa; de lo contrario, la coincidencia falla.

La razón por la que el algoritmo BF es lento es que hay muchos retrocesos innecesarios, es decir, después de que falla un determinado proceso de coincidencia con t, es necesario volver al siguiente carácter del carácter inicial. de la cadena s y comenzar la comparación nuevamente, lo cual no es necesario para Ciertas cadenas de patrones son innecesarias. Por ejemplo, si s=12123123132, t=12313, cuando t se compara con la subsecuencia en negrita en 12 12312 3132, se produce una falta de coincidencia en 2 y el algoritmo BF luego comparará t con 121 23123 132, 1212 31231 32, 12123 12313. 2 comparación. Dado que 231 y 312 en t no son lo mismo que el 123 inicial, obviamente la comparación entre t y 121 23123 132 y 1212 31231 32 es innecesaria.

El algoritmo KMP utiliza la repetición de las subcadenas al principio de la cadena del patrón para reducir el retroceso repetido y lograr un salto directo a una nueva ronda de comparación. Específicamente, el algoritmo KMP utiliza una matriz para registrar cuántos caracteres delante de cada carácter en la cadena del patrón se repiten desde el principio de la cadena del patrón. Cuando se compara con la cadena s y hay una discrepancia, salta directamente a la siguiente. carácter de la subcadena repetida y continúa la comparación en lugar de saltar al carácter 0 de la cadena de patrón t.

Pasos del algoritmo: ① Calcule la matriz de salto a continuación. ② Utilice el algoritmo KMP para la coincidencia de patrones.

La siguiente matriz se calcula mediante recursividad, es decir, si el carácter anterior t[j-1] del carácter actual t[j] es el carácter t[siguiente[j-1] señalado por su next[j-1] ] es el mismo, lo que significa que los next[j-1]+1 caracteres antes de t[j] son ​​los mismos que la subcadena de t[0] a t[next[j-1] ], entonces next[j]=next[ j-1]+1; si no son iguales, recurra al carácter señalado por el siguiente valor de t[next[j-1]] y compárelo con t. [j-1] hasta que se confirme t[j] con la cadena t El número de caracteres repetidos desde el principio, o ningún carácter repetido marcado como 0.

Tenga en cuenta que el tipo de parámetro de retorno de la función aquí es int*, que se utiliza para devolver una matriz de un bit, y la matriz de un bit devuelta debe definirse estáticamente en la función.

Cuando el algoritmo KMP realiza una coincidencia de patrones, solo necesita asignar el puntero j al siguiente [j] durante el retroceso. Cabe señalar que si el siguiente [j] es -1, significa que no hay ningún carácter repetido desde el principio de t [j], y t [j] y s [i] no coinciden, entonces i y j agrega 1 .

Considerar más cadenas de patrones especiales puede reducir aún más el retroceso innecesario. Por ejemplo, s = 111211112, t = 11112, según el método de cálculo anterior, siguiente = {-1,0,1,2,3}. Cuando i = 3, j = 3, hay una falta de coincidencia. En este momento, s [i] = 2, t [j] = 1. Como el siguiente [j] = 2, j salta a 2, t = 11 1 12. y s =111 2 11112 comparar. Dado que t[next[j]]=t[j] también es 1, debe ser diferente de s[i]=2. Obviamente, este retroceso no es necesario.

En resumen, cuando el carácter que no coincide es el mismo que el carácter que se va a saltar, no tiene sentido saltar un paso. Puede saltar otro paso, es decir, establecer el carácter actual en el siguiente valor de. el personaje después del salto.