Complejidad temporal del algoritmo kmp
El algoritmo KMP es un algoritmo mejorado de coincidencia de cadenas propuesto por D.E.Knuth, J.H.Morris y V.R.Pratt, por lo que se denomina operación Knut-Morris-Pratt (algoritmo KMP para abreviar). El núcleo del algoritmo KMP es utilizar la información después de que la coincidencia falla para minimizar el número de coincidencias entre la cadena de patrón y la cadena principal para lograr una coincidencia rápida. La complejidad temporal del algoritmo KMP es O (m + n).
Lo primero que me viene a la mente debe ser un método simple, comenzando desde cada elemento, pero la complejidad puede alcanzar O (m * n) bajo datos poco amigables, y definitivamente despegará. Entonces, ¿cómo optimizar? ¿Pensando en lo que se repite en ejercicios sencillos? Por ejemplo, para comprender: cadena de patrón: abcabc, cadena de texto: abcabdababcabc.
Primero piensa brevemente y luego explora... abcab. Los siguientes cyd no coinciden, entonces, de acuerdo con el algoritmo simple, ¿deberíamos reiniciar la coincidencia hacia la derecha?
Pero fíjate bien, en el abcab buscado, ¿podemos seguir haciendo coincidir solo moviéndonos 3 pasos hacia la derecha, es decir, moviéndonos al último ab? Luego registre el mismo prefijo abc, de modo que pueda saltar directamente del abc anterior al siguiente. Ésta es la esencia del pensamiento KMP. Después de que la coincidencia falle, no buscaremos hacia atrás paso a paso, sino que buscaremos un sufijo común durante la búsqueda y comenzaremos la búsqueda.
Análisis de complejidad temporal de KMP:
Supongamos que m es la longitud de la cadena de patrón strM y n es la longitud de la cadena strN que debe coincidir. O(m+n)+O([m, 2m]+[n, 2n]) = complejidad temporal de calcular la siguiente matriz + complejidad de comparación transversal. Es decir, el número de comparaciones al calcular la siguiente matriz está entre [m, 2m]. El número de comparaciones para la comparación transversal está entre [n, 2n], y el peor de los casos es T = "AAAABAAAAB" y P = "AAAAA". Entonces la complejidad temporal del algoritmo es O (m + n).
Aquí analizamos cómo obtener el peor caso de [n, 2n]. Se puede entender de manera abstracta que al atravesar la cadena strN para hacer coincidir, las situaciones posibles al comparar strN [i] y strM [j] son las siguientes:
1 Cuando el carácter actual coincide, mueva i++. yj++. 2. Si el carácter actual no coincide y j = 0, solo se mueve i ++ y j = 0 no se mueve. 3. El personaje actual no coincide y J! Cuando = 0, I permanece sin cambios, strM[j] puede rebotar como máximo j veces, pero j está determinado por el caso coincidente 1. El caso 1 no siempre puede * * * exceder n veces, por lo que el rebote total no excederá n veces. Entonces, en el peor de los casos, i++ veces (caso 1 + caso 2) + j rebote (caso 3) = n + peor caso n = 2n. [m, 2m] también se puede demostrar de manera similar.