Complejidad del tiempo del algoritmo Kmp

La complejidad temporal del algoritmo KMP es O(m+n)?.

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 la gente lo llama algoritmo de operación Knuth-Morris-Pratt (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 enfoque simple, comenzando desde cada elemento, pero la complejidad puede alcanzar O (m * n) con datos poco amigables, lo que definitivamente despegará. Entonces, ¿cómo optimizar? ¿Piensa en lo que se repite en prácticas sencillas? Tome un ejemplo y comprenderá: cadena de patrón: abcabc, cadena de texto: abcabdababcabc.

Empieza con una idea sencilla y busca de principio a fin... abcab. Los siguientes cyd no coinciden, por lo que, de acuerdo con el algoritmo simple, ¿necesitamos reiniciar la posición coincidente hacia la derecha?

Pero mira más de cerca en el abcab que se ha buscado, ¿es necesario avanzar 3 pasos hacia la derecha, es decir, hasta el ab del final, para seguir haciendo coincidir? Luego registre el mismo sufijo abc, de modo que pueda saltar directamente del abc anterior al siguiente. Esta es la esencia de la idea de KMP. Después de que falla una coincidencia, no buscará hacia atrás paso a paso, sino que utilizará el proceso de búsqueda para encontrar un sufijo público y comenzar a buscar.

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 la 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 es entre [n, 2n], y el peor de los casos es como T = "aaaabaaaab", P = "aaaaa". Entonces la complejidad temporal del algoritmo es O (m + n).

Aquí hay un análisis de cómo se deriva el peor caso de [n, 2n]. Se puede entender de forma abstracta al atravesar la cadena strN que se va a comparar, al comparar strN[i] y. strM[j] Las situaciones posibles son:

1. Cuando el carácter actual coincide, mueva i++ y j++ al mismo tiempo. 2. Cuando el carácter actual no coincide y j = 0, solo se mueve i ++ y j = 0 no se mueve. 3. El carácter actual no coincide, y cuando j! = 0, i permanece sin cambios, strM [j] salta hacia atrás, hasta j veces, pero j está determinado por el caso 1 coincidente anterior, y el caso 1 es absolutamente imposible de ocurrir más de 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 n = 2n. [m,2m] también se puede demostrar de manera similar.