Programación Java para implementar la coincidencia de patrones de cadenas

El algoritmo de coincidencia de patrones de cadena tradicional (es decir, el algoritmo BF) consiste en comparar la cadena principal y la cadena de patrón de izquierda a derecha carácter por carácter. Si no coinciden, los punteros de posición del. Se comparan la cadena principal y la cadena del patrón. Todo vuelve atrás. La complejidad temporal de dicho algoritmo es O (n*m), donde n y m son las longitudes de la cadena s y la cadena t respectivamente.

El algoritmo KMP fue propuesto conjuntamente por Knuth, Morris y Pratt, por lo que se convirtió en el algoritmo Knuth-Morris-Pratt, conocido como algoritmo KMP. El algoritmo KMP es un algoritmo clásico en la coincidencia de patrones de cadenas. En comparación con el algoritmo BF, la diferencia del algoritmo KMP es que durante el proceso de coincidencia, el puntero de posición de la cadena principal no se rastreará. Como resultado, la complejidad temporal del algoritmo es solo O (n + m). .