En informática , el algoritmo de búsqueda de cadenas de Knuth-Morris-Pratt (o algoritmo KMP ) busca apariciones de una "palabra" W
dentro de una "cadena de texto" principal S
mediante la observación de que cuando se produce una discrepancia, la palabra en sí contiene suficiente información para determinar dónde podría comenzar la siguiente coincidencia, evitando así el reexamen de los caracteres previamente emparejados.
Clase | Búsqueda de cadenas |
---|---|
Estructura de datos | Cuerda |
Rendimiento en el peor de los casos | Θ (m) preprocesamiento + Θ (n) coincidencia [nota 1] |
Complejidad espacial en el peor de los casos | Θ (m) |
El algoritmo fue concebido por James H. Morris y descubierto de forma independiente por Donald Knuth "unas semanas después" a partir de la teoría de los autómatas . [1] [2] Morris y Vaughan Pratt publicaron un informe técnico en 1970. [3] Los tres también publicaron el algoritmo conjuntamente en 1977. [1] Independientemente, en 1969, Matiyasevich [4] [5] descubrió un algoritmo similar, codificado por una máquina de Turing bidimensional, mientras estudiaba un problema de reconocimiento de coincidencia de patrones de cuerdas sobre un alfabeto binario. Este fue el primer algoritmo de tiempo lineal para la coincidencia de cadenas. [6]
Fondo
Un algoritmo de coincidencia de cadenas desea encontrar el índice inicial m
en una cadena S[]
que coincida con la palabra de búsqueda W[]
.
El algoritmo más sencillo, conocido como algoritmo de " fuerza bruta " o "ingenuo", es buscar una palabra que coincida en cada índice m
, es decir, la posición en la cadena que se busca que corresponde al carácter S[m]
. En cada posición, m
el algoritmo comprueba primero la igualdad del primer carácter de la palabra que se busca, es decir S[m] =? W[0]
. Si se encuentra una coincidencia, el algoritmo pone a prueba los otros caracteres de la palabra que se busca mediante la comprobación de valores sucesivos de la posición de índice de la palabra, i
. El algoritmo recupera el carácter W[i]
de la palabra que se busca y comprueba la igualdad de la expresión S[m+i] =? W[i]
. Si todos los caracteres sucesivos coinciden en la W
posición m
, entonces se encuentra una coincidencia en esa posición en la cadena de búsqueda. Si el índice m
llega al final de la cadena, entonces no hay coincidencia, en cuyo caso se dice que la búsqueda "falla".
Por lo general, la verificación de prueba rechazará rápidamente la coincidencia de prueba. Si las cadenas son letras aleatorias distribuidas uniformemente, entonces la probabilidad de que los caracteres coincidan es de 1 en 26. En la mayoría de los casos, la verificación de prueba rechazará la coincidencia en la letra inicial. La probabilidad de que las dos primeras letras coincidan es de 1 en 26 2 (1 en 676). Entonces, si los caracteres son aleatorios, entonces la complejidad esperada de buscar una cadena S[]
de longitud n es del orden de n comparaciones o O ( n ). El rendimiento esperado es muy bueno. Si S[]
tiene 1 millón de caracteres y W[]
1000 caracteres, la búsqueda de cadenas debería completarse después de aproximadamente 1,04 millones de comparaciones de caracteres.
Ese rendimiento esperado no está garantizado. Si las cadenas no son aleatorias, la verificación de una prueba m
puede requerir muchas comparaciones de caracteres. El peor de los casos es si las dos cadenas coinciden en todas menos la última letra. Imagine que la cadena S[]
consta de 1 millón de caracteres que son todos A y que la palabra W[]
tiene 999 caracteres A que terminan en un carácter B final . El algoritmo de coincidencia de cadenas simple ahora examinará 1000 caracteres en cada posición de prueba antes de rechazar la coincidencia y avanzar a la posición de prueba. El ejemplo de búsqueda de cadena simple ahora tomaría aproximadamente 1000 comparaciones de caracteres multiplicadas por 1 millón de posiciones para 1000 millones de comparaciones de caracteres. Si la longitud de W[]
es k , entonces el desempeño en el peor de los casos es O ( k ⋅ n ).
El algoritmo KMP tiene un mejor rendimiento en el peor de los casos que el algoritmo sencillo. KMP dedica un poco de tiempo a precalcular una tabla (del orden del tamaño de W[]
, O ( k )), y luego usa esa tabla para hacer una búsqueda eficiente de la cadena en O ( n ).
La diferencia es que KMP utiliza información de coincidencia previa que el algoritmo sencillo no hace. En el ejemplo anterior, cuando KMP ve que una coincidencia de prueba falla en el carácter 1000 ( i
= 999) porque S[m+999] ≠ W[999]
aumentará m
en 1, pero sabrá que los primeros 998 caracteres en la nueva posición ya coinciden. KMP coincidió con los caracteres 999 A antes de descubrir una discrepancia en el carácter 1000 (posición 999). Al avanzar la posición de prueba de coincidencia m
en uno se descarta la primera A , por lo que KMP sabe que hay 998 caracteres A que coinciden W[]
y no los vuelve a probar; es decir, KMP se establece i
en 998. KMP mantiene su conocimiento en la tabla precalculada y dos variables de estado. Cuando KMP descubre una discrepancia, la tabla determina cuánto KMP aumentará (variable m
) y dónde se reanudarán las pruebas (variable i
).
Algoritmo KMP
Ejemplo del algoritmo de búsqueda
Para ilustrar los detalles del algoritmo, considere una ejecución (relativamente artificial) del algoritmo, donde W
= "ABCDABD" y S
= "ABC ABCDAB ABCDABCDABDE". En un momento dado, el algoritmo se encuentra en un estado determinado por dos números enteros:
m
, que denota la posición dentro deS
dondeW
comienza la coincidencia prospectiva ,i
, que denota el índice del carácter considerado actualmente enW
.
En cada paso, el algoritmo compara S[m+i]
con W[i]
y incrementos i
si son iguales. Esto se representa, al comienzo de la ejecución, como
1 2 m: 01234567890123456789012S: ABC ABCDAB ABCDABCDABDE W: ABC D ABD i: 012 3 456
El algoritmo compara los caracteres sucesivos de con los caracteres W
"paralelos" de S
, pasando de uno a otro aumentando i
si coinciden. Sin embargo, en el cuarto paso S[3] = ' '
no coincide W[3] = 'D'
. En lugar de comenzar a buscar nuevamente en S[1]
, notamos que no 'A'
ocurre entre las posiciones 1 y 2 en S
; por lo tanto, habiendo verificado todos esos caracteres previamente (y sabiendo que coincidieron con los caracteres correspondientes en W
), no hay posibilidad de encontrar el comienzo de una coincidencia. Por lo tanto, el algoritmo establece m = 3
y i = 0
.
1 2 m: 01234567890123456789012S: ABC ABCDAB ABCDABCDABDE W: A BCDABD i: 0 123456
Esta coincidencia falla en el carácter inicial, por lo que el algoritmo establece m = 4
yi = 0
1 2 m: 01234567890123456789012S: ABC ABCDAB ABCDABCDABDE W: ABCDAB D i: 012345 6
Aquí, se i
incrementa a través de una coincidencia casi completa "ABCDAB"
hasta i = 6
dar una discrepancia en W[6]
y S[10]
. Sin embargo, justo antes del final de la coincidencia parcial actual, existía esa subcadena "AB"
que podría ser el comienzo de una nueva coincidencia, por lo que el algoritmo debe tener esto en cuenta. Como estos caracteres coinciden con los dos caracteres anteriores a la posición actual, no es necesario volver a comprobar esos caracteres; el algoritmo establece m = 8
(el comienzo del prefijo inicial) y i = 2
(lo que indica que los dos primeros caracteres coinciden) y continúa haciendo coincidir. Por lo tanto, el algoritmo no solo omite los caracteres previamente emparejados de S
(el "AB"
), sino también los caracteres previamente emparejados de W
(el prefijo "AB"
).
1 2 m: 01234567890123456789012S: ABC ABCD AB ABCDABCDABDE W: AB C DABD i: 01 2 3456
Esta búsqueda en la nueva posición falla inmediatamente porque W[2]
(a 'C'
) no coincide con S[10]
(a ' '
). Como en la primera prueba, la discrepancia hace que el algoritmo vuelva al principio de W
y comience a buscar en la posición del carácter no coincidente de S
:, m = 10
reset i = 0
.
1 2 m: 01234567890123456789012S: ABC ABCDAB ABCDABCDABDE W: A BCDABD i: 0 123456
La coincidencia en m=10
falla inmediatamente, por lo que el algoritmo intenta a continuación m = 11
y i = 0
.
1 2 m: 01234567890123456789012S: ABC ABCDAB ABCDAB C DABDE W: ABCDAB D i: 012345 6
Una vez más, el algoritmo coincide "ABCDAB"
, pero el siguiente carácter, 'C'
no coincide con el carácter final 'D'
de la palabra W
. Razonando como antes, el algoritmo establece m = 15
, para comenzar en la cadena de dos caracteres que "AB"
conduce a la posición actual, establece i = 2
y continúa haciendo coincidir desde la posición actual.
1 2 m: 01234567890123456789012S: ABC ABCDAB ABCD ABCDABD E W: ABCDABD i: 0123456
Esta vez el partido está completo, y el primer personaje del partido es S[15]
.
Descripción del pseudocódigo para el algoritmo de búsqueda
El ejemplo anterior contiene todos los elementos del algoritmo. Por el momento, asumimos la existencia de una tabla de "coincidencia parcial" T
, que se describe a continuación , que indica dónde debemos buscar el inicio de una nueva coincidencia cuando se encuentra una falta de coincidencia. Las entradas de T
están construidas de modo que si tenemos una coincidencia que comienza en S[m]
que falla al comparar S[m + i]
con W[i]
, entonces la siguiente coincidencia posible comenzará en el índice m + i - T[i]
en S
(es decir, T[i]
es la cantidad de "retroceso" que necesitamos hacer después de una falta de coincidencia). Esto tiene dos implicaciones: primero, T[0] = -1
que indica que si W[0]
hay una falta de coincidencia, no podemos retroceder y simplemente debemos marcar el siguiente carácter; y en segundo lugar, aunque la siguiente coincidencia posible comenzará en index m + i - T[i]
, como en el ejemplo anterior, no es necesario que verifiquemos ninguno de los T[i]
caracteres después de eso, para continuar buscando desde W[T[i]]
. A continuación, se muestra una implementación de pseudocódigo de muestra del algoritmo de búsqueda KMP.
algoritmo kmp_search : entrada : una matriz de caracteres, S (el texto que se buscará) una serie de caracteres, W (la palabra buscada) salida : una matriz de números enteros, P (posiciones en S en las que se encuentra W) un número entero, nP (número de posiciones) definir variables : un número entero, j ← 0 (la posición del carácter actual en S) un número entero, k ← 0 (la posición del carácter actual en W) una matriz de números enteros, T (la tabla, calculada en otro lugar) sea nP ← 0 mientras que jhacer si W [k] = S [j] entonces sea j ← j + 1 sea k ← k + 1 si k = longitud (W) entonces (ocurrencia encontrada, si solo se necesita la primera ocurrencia, m ← j - k se puede devolver aquí) sea P [nP] ← j - k, nP ← nP + 1 sea k ← T [k] (T [longitud (W)] no puede ser -1) de lo contrario sea k ← T [k] si k <0 entonces sea j ← j + 1 sea k ← k + 1
Eficiencia del algoritmo de búsqueda
Suponiendo la existencia previa de la tabla T
, la parte de búsqueda del algoritmo de Knuth-Morris-Pratt tiene complejidad O ( n ) , donde n es la longitud de S
y la O es la notación O grande . A excepción de los gastos generales fijos incurridos al entrar y salir de la función, todos los cálculos se realizan en el while
ciclo. Para limitar el número de iteraciones de este bucle; observe que T
está construido de modo que si una coincidencia que había comenzado en S[m]
falla mientras se compara S[m + i]
con W[i]
, entonces la siguiente coincidencia posible debe comenzar en S[m + (i - T[i])]
. En particular, la siguiente coincidencia posible debe ocurrir en un índice más alto que m
, de modo que T[i] < i
.
Este hecho implica que el ciclo puede ejecutarse como máximo 2 n veces, ya que en cada iteración ejecuta una de las dos ramas del ciclo. La primera rama aumenta invariablemente i
y no cambia m
, de modo que aumenta el índice m + i
del carácter actualmente examinado de S
. La segunda rama se suma i - T[i]
a m
, y como hemos visto, este es siempre un número positivo. Por lo tanto, m
se incrementa la ubicación del comienzo de la coincidencia potencial actual. Al mismo tiempo, la segunda rama m + i
no cambia, m
se le i - T[i]
agrega, e inmediatamente después T[i]
se asigna como el nuevo valor de i
, por lo tanto new_m + new_i = old_m + old_i - T[old_i] + T[old_i] = old_m + old_i
. Ahora, el ciclo termina si m + i
= n ; por lo tanto, cada rama del bucle se puede alcanzar como máximo n veces, ya que respectivamente aumentan m + i
o m
, y m ≤ m + i
: si m
= n , entonces ciertamente m + i
≥ n , de modo que dado que aumenta en incrementos unitarios como máximo, debemos haber tenido m + i
= n en algún momento del pasado y, por lo tanto, de cualquier manera habríamos terminado.
Por tanto, el ciclo se ejecuta como máximo 2 n veces, lo que muestra que la complejidad temporal del algoritmo de búsqueda es O ( n ).
Aquí hay otra forma de pensar sobre el tiempo de ejecución: digamos que comenzamos a coincidir W
y S
en la posición i
y p
. Si W
existe como una subcadena de S
en p, entonces W[0..m] = S[p..p+m]
. En caso de éxito, es decir, la palabra y el texto coinciden en las posiciones ( W[i] = S[p+i]
), aumentamos i
en 1. Si falla, es decir, la palabra y el texto no coinciden en las posiciones ( W[i] ≠ S[p+i]
), el puntero de texto se mantiene quieto, mientras que la palabra puntero se revierte una cierta cantidad ( i = T[i]
, donde T
está la tabla de salto), e intentamos hacer coincidir W[T[i]]
con S[p+i]
. El número máximo de retroceso de i
está limitado por i
, es decir, para cualquier falla, solo podemos retroceder tanto como hayamos progresado hasta la falla. Entonces está claro que el tiempo de ejecución es 2 n .
Tabla "Coincidencia parcial" (también conocida como "función de falla")
El objetivo de la tabla es permitir que el algoritmo no coincida con ningún carácter de S
más de una vez. La observación clave sobre la naturaleza de una búsqueda lineal que permite que esto suceda es que, al haber verificado algún segmento de la cadena principal con un segmento inicial del patrón, sabemos exactamente en qué lugares se ubica una nueva coincidencia potencial que podría continuar con la actual. posición podría comenzar antes que la posición actual. En otras palabras, "pre-buscamos" el patrón en sí y compilamos una lista de todas las posibles posiciones de respaldo que omiten un máximo de caracteres desesperados sin sacrificar ninguna coincidencia potencial al hacerlo.
Queremos poder buscar, para cada posición en W
, la longitud del segmento inicial más largo posible que W
conduce a (pero sin incluir) esa posición, que no sea el segmento completo que comienza en el W[0]
que simplemente no coincidió; esto es lo lejos que tenemos que retroceder para encontrar la siguiente coincidencia. Por T[i]
lo tanto, es exactamente la longitud del segmento inicial propio más largo posible del W
cual también es un segmento de la subcadena que termina en W[i - 1]
. Usamos la convención de que la cadena vacía tiene longitud 0. Dado que una falta de coincidencia al comienzo del patrón es un caso especial (no hay posibilidad de retroceso), establecemos T[0] = -1
, como se explica a continuación .
Ejemplo de trabajo del algoritmo de construcción de tablas
Consideramos el ejemplo de W = "ABCDABD"
first. Veremos que sigue el mismo patrón que la búsqueda principal y es eficiente por razones similares. Ponemos T[0] = -1
. Para encontrarlo T[1]
, debemos descubrir un sufijo propio del "A"
cual también es un prefijo de patrón W
. Pero no hay sufijos adecuados de "A"
, por lo que establecemos T[1] = 0
. Para encontrar T[2]
, vemos que la subcadena W[0]
- W[1]
( "AB"
) tiene un sufijo adecuado "B"
. Sin embargo, "B" no es un prefijo del patrón W
. Por lo tanto, establecemos T[2] = 0
.
Continuando T[3]
, primero verificamos el sufijo adecuado de longitud 1, y como en el caso anterior falla. ¿Deberíamos comprobar también los sufijos más largos? No, ahora notamos que hay un atajo para verificar todos los sufijos: digamos que descubrimos un sufijo adecuado que es un prefijo adecuado (un prefijo adecuado de una cadena no es igual a la cadena en sí) y que termina en W[2]
con longitud 2 (el máximo posible); entonces su primer carácter es también un prefijo adecuado de W
, por lo tanto, un prefijo adecuado en sí mismo, y termina en W[1]
, que ya determinamos que no ocurrió como T[2] = 0
y no T[2] = 1
. Por lo tanto, en cada etapa, la regla de acceso directo es que uno debe considerar verificar los sufijos de un tamaño dado m + 1 solo si se encontró un sufijo válido de tamaño m en la etapa anterior (es decir T[x] = m
) y no debe molestarse en verificar m + 2, m + 3, etc.
Por lo tanto, ni siquiera debemos preocuparnos por las subcadenas de longitud 2 y, como en el caso anterior, falla la única de longitud 1 T[3] = 0
.
Pasamos a la posterior W[4]
, 'A'
. La misma lógica muestra que la subcadena más larga que debemos considerar tiene una longitud de 1 y, como en el caso anterior, falla ya que "D" no es un prefijo de W
. Pero en lugar de establecer T[4] = 0
, podemos hacerlo mejor si notamos que W[4] = W[0]
, y también que una búsqueda de T[4]
implica el S
carácter correspondiente S[m+4]
, hubo una falta de coincidencia y, por lo tanto S[m+4] ≠ 'A'
. Por tanto, no tiene sentido reiniciar la búsqueda en S[m+4]
; debemos comenzar en 1 posición por delante. Esto significa que podemos cambiar el patrón W
por longitud de coincidencia más un carácter, entonces T[4] = -1
.
Considerando ahora el siguiente carácter, W[5]
que es 'B'
: aunque por inspección la subcadena más larga parecería ser 'A'
, seguimos estableciendo T[5] = 0
. El razonamiento es similar al por qué T[4] = -1
. W[5]
sí se extiende el partido prefijo comenzado con W[4]
, y podemos suponer que el carácter correspondiente en S
, S[m+5] ≠ 'B'
. Entonces, retroceder antes no W[5]
tiene sentido, pero S[m+5]
puede ser 'A'
, por lo tanto T[5] = 0
.
Finalmente, vemos que el siguiente personaje en el segmento en curso que comienza en W[4] = 'A'
sería 'B'
, y de hecho también lo es W[5]
. Además, el mismo argumento anterior muestra que no necesitamos buscar antes W[4]
para encontrar un segmento W[6]
, por lo que es este, y tomamos T[6] = 2
.
Por tanto, compilamos la siguiente tabla:
i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
---|---|---|---|---|---|---|---|---|
W[i] | A | B | C | D | A | B | D | |
T[i] | -1 | 0 | 0 | 0 | -1 | 0 | 2 | 0 |
Otro ejemplo:
i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
---|---|---|---|---|---|---|---|---|---|---|
W[i] | A | B | A | C | A | B | A | B | C | |
T[i] | -1 | 0 | -1 | 1 | -1 | 0 | -1 | 3 | 2 | 0 |
Otro ejemplo (ligeramente modificado con respecto al ejemplo anterior):
i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
---|---|---|---|---|---|---|---|---|---|---|
W[i] | A | B | A | C | A | B | A | B | A | |
T[i] | -1 | 0 | -1 | 1 | -1 | 0 | -1 | 3 | -1 | 3 |
Otro ejemplo más complicado:
i | 00 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 | 13 | 14 | 15 | dieciséis | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
W[i] | PAG | A | R | T | I | C | I | PAG | A | T | mi | I | norte | PAG | A | R | A | C | H | U | T | mi | |||
T[i] | -1 | 0 | 0 | 0 | 0 | 0 | 0 | -1 | 0 | 2 | 0 | 0 | 0 | 0 | 0 | -1 | 0 | 0 | 3 | 0 | 0 | 0 | 0 | 0 | 0 |
Descripción del pseudocódigo para el algoritmo de creación de tablas
El ejemplo anterior ilustra la técnica general para ensamblar la mesa con un mínimo de esfuerzo. El principio es el de la búsqueda general: la mayor parte del trabajo ya se había hecho para llegar al puesto actual, por lo que se necesita muy poco para dejarlo. La única complicación menor es que la lógica que es correcta al final de la cadena da erróneamente subcadenas no adecuadas al principio. Esto requiere algún código de inicialización.
algoritmo kmp_table : entrada : una matriz de caracteres, W (la palabra a analizar) salida : una matriz de números enteros, T (la tabla que se va a llenar) definir variables : un número entero, pos ← 1 (la posición actual que estamos calculando en T) un número entero, cnd ← 0 (el índice de base cero en W del siguiente carácter de la subcadena candidata actual) sea T [0] ← -1 while poshacer si W [pos] = W [cnd] luego dejar T [pos] ← T [cnd] de lo contrario dejar T [pos] ← cnd mientras cnd ≥ 0 y W [pos] ≠ W [cnd ] no deja CND ← T [CND] dejó pos pos ← + 1, CND CND ← + 1 let T [pos] ← cnd (solo es necesario cuando se buscan todas las apariciones de palabras)
Eficiencia del algoritmo de construcción de tablas
La complejidad temporal (y por tanto espacial) del algoritmo de la tabla es , dónde es la longitud de W
.
- El bucle externo:
pos
se inicializa a 1, la condición del bucle espos < k
, ypos
se incrementa en 1 en cada iteración del bucle. Así el bucle tomará iteraciones.
- El bucle interno:
cnd
se inicializa0
y se incrementa como máximo en 1 en cada iteración del bucle externo.T[cnd]
es siempre menor quecnd
, por lo quecnd
se reduce en al menos 1 en cada iteración del ciclo interno; la condición del bucle interno escnd ≥ 0
. Esto significa que el bucle interno se puede ejecutar como máximo tantas veces en total como se ha ejecutado el bucle externo; cada disminución decnd
en 1 en el bucle interno debe tener un aumento correspondiente en 1 en el bucle externo. Dado que el bucle exterior toma iteraciones, el bucle interno no puede tomar más de iteraciones en total.
Combinados, los bucles exterior e interior toman como máximo iteraciones. Esto corresponde acomplejidad del tiempo usando la notación O grande .
Eficiencia del algoritmo KMP
Dado que las dos partes del algoritmo tienen, respectivamente, complejidades de O(k)
y O(n)
, la complejidad del algoritmo general es O(n + k)
.
Estas complejidades son las mismas, sin importar cuántos patrones repetitivos haya en W
o S
.
Variantes
Se puede implementar una versión en tiempo real de KMP utilizando una tabla de función de falla separada para cada carácter del alfabeto. Si ocurre una discrepancia en el personaje en el texto, la tabla de función de falla para el carácter se consulta para el índice en el patrón en el que se produjo el desajuste. Esto devolverá la longitud de la subcadena más larga que termina en coincidir con un prefijo del patrón, con la condición añadida de que el carácter después del prefijo sea . Con esta restricción, el personajeen el texto no es necesario volver a comprobarlo en la siguiente fase, por lo que sólo se ejecuta un número constante de operaciones entre el procesamiento de cada índice del texto [ cita requerida ] . Esto satisface la restricción de computación en tiempo real.
El algoritmo de Booth usa una versión modificada de la función de preprocesamiento KMP para encontrar la rotación de cadena mínima lexicográficamente . La función de falla se calcula progresivamente a medida que se gira la cuerda.
Notas
- ^ m es la longitud del patrón, que es la cadena que estamos buscando en el texto que tiene una longitud n
Referencias
- ^ a b Knuth, Donald; Morris, James H .; Pratt, Vaughan (1977). "Emparejamiento rápido de patrones en cadenas". Revista SIAM de Computación . 6 (2): 323–350. CiteSeerX 10.1.1.93.8147 . doi : 10.1137 / 0206024 .
- ^ Knuth, Donald E. (1973). "Los peligros de la teoría de la informática". Estudios de Lógica y Fundamentos de las Matemáticas . 74 : 189-195. doi : 10.1016 / S0049-237X (09) 70357-X . ISBN 9780444104915.
- ^ Morris, JH, Jr; Pratt, V. (1970). Un algoritmo de coincidencia de patrones lineales (informe técnico). Universidad de California, Berkeley, Centro de Computación. TR-40.
- ^ Матиясевич, Юрий (1971). "О распознавании в реальное время отношения вхождения" (PDF) . Записки научных семинаров Ленинградского отделения Математического института им. В.А.Стеклова (en ruso). 20 : 104-114., traducido al inglés como Matiyasevich, Yuri (1973). "Reconocimiento en tiempo real de la relación de inclusión" . Revista de matemáticas soviéticas . 1 : 64–70. doi : 10.1007 / BF01117471 .
- ↑ Knuth menciona este hecho en la errata de su libro Selected Papers on Design of Algorithms :
En 2012 supe que Yuri Matiyasevich había anticipado los algoritmos de coincidencia de patrones en tiempo lineal y de preprocesamiento de patrones de este artículo, en el caso especial de un alfabeto binario, ya en 1969. Los presentó como construcciones para una máquina de Turing con una estructura bidimensional. memoria de trabajo.
- ^ Amir, Amihood; Landau, Gad M .; Lewenstein, Moshe; Sokol, Dina (2007). "Texto dinámico y coincidencia de patrones estáticos". ACM Trans. Algoritmos . 3 (2): 19. doi : 10.1145 / 1240233.1240242 .
- Cormen, Thomas ; Leiserson, Charles E .; Rivest, Ronald L .; Stein, Clifford (2001). "Sección 32.4: El algoritmo de Knuth-Morris-Pratt". Introducción a los algoritmos (Segunda ed.). MIT Press y McGraw-Hill. págs. 923 –931. ISBN 0-262-03293-7. Zbl 1047.68161 .
- Crochemore, Maxime; Rytter, Wojciech (2003). Joyas de la cuerda. Algoritmos de texto . River Edge, Nueva Jersey: World Scientific. págs. 20-25. ISBN 981-02-4897-0. Zbl 1078.68151 .
- Szpankowski, Wojciech (2001). Análisis de caso medio de algoritmos sobre secuencias . Serie Wiley-Interscience en matemáticas discretas y optimización. Con prólogo de Philippe Flajolet. Chichester: Wiley. págs. 15-17, 136-141. ISBN 0-471-24063-X. Zbl 0968.68205 .
enlaces externos
- Animación del subprograma de búsqueda de cadenas
- Una explicación del algoritmo y código C ++ de muestra por David Eppstein
- Descripción del algoritmo Knuth-Morris-Pratt y código C por Christian Charras y Thierry Lecroq
- Explicación del algoritmo desde cero por FH Flensburg.
- Desglosando los pasos de ejecutar KMP por Chu-Cheng Hsieh.
- Video de la conferencia de YouTube NPTELHRD
- Video de la conferencia de LogicFirst YouTube
- Prueba de corrección
- Transformación entre diferentes formas de algoritmo
- Algoritmo de Knuth-Morris-Pratt escrito en C #