La búsqueda se lleva a cabo utilizando información basada en los fallos previos.
Supongamos una tabla 'F' ya precalculada, y supongamos que el patrón a buscar esté contenido en la matriz 'P()', y la cadena donde buscamos esté contenida en la matriz 'T()'.
En cuanto al primero, por necesidad se marca -1, pues de ese modo le es imposible regresar más atrás, sino siempre adelante (el valor que contiene la tabla siempre se usa restando en la función de búsqueda, luego restar un -1, supone en efecto sumar 1 y por tanto avanza).
La capacidad del algoritmo (para demostrar que no examina caracteres más de dos veces) queda patente al apreciar como logra saltar varios caracteres a la vez cuando hay un fallo.
Esto se aprecia mejor, mirando la tabla 'F', cuantos mayor es el valor en la tabla tanto más grande es el salto resultante (salto debido a que dichos caracteres ya han sido examinados) y cuantos más ceros haya, señala que ha ido avanzando el puntero absoluto de uno en uno.
En la práctica el algoritmo no será mucho mejor que el algoritmo lineal de fuerza bruta, en condicioes normales (texto del lenguaje hablado, por ejemplo), pero mejora sustancialmente, respecto del mismo cuando sale de dichas condiciones normales, en tanto que algoritmo presente no presenta demasiada sobrecarga.
Respecto del patrón, no existe caso mejor ni peor (considerado por sí solo), puede demostrarse que en una tabla de fallos donde son todo ceros (o lo que es lo mismo, el primer carácter del patrón aparece una única vez (por ejemplo P ="ABBBBBBB")), tiene el mismo coste que cuando el patrón se compone de 2 únicos caracteres donde 1 se repite en todo el patrón y el otro aparece al final, (por ejemplo: P= "AAAAAAAB", (obsérvese la tabla F para dicho texto)) y tiene el mismo coste que en cualquier otra situación intermedia entre dichos extremos: En el caso de que el primer carácter aparezca una única vez (ver tabla aquí debajo), examina la A, si coincide, examina la B, en caso de fallo simplemente salta 1 carácter.
La diferencia entre uno y otro casos consiste básicamente en donde se localiza el puntero en el patrón y en qué momento se recorre el resto del patrón si al principio o al final del texto.
Cada carácter fallido necesita ser comprobado otra vez con aquel con el que se alinea.
Esto implica que el peor caso puede llegar a tener un costo de O(n) + O(k*2), si bien en la práctica estos casos son raros, pues no es frecuente que deban realizarse búsqueda con patrones o textos cuyos caracteres tengan una alta frecuencia de reptición (como los que s emuestran de ejemplo a continuación)..
Por tanto en la siguiente figura avanzamos hasta la posición absoluta de T actual, 3.
Volvemos al principio del bucle (cada vez que se vuelve a este punto se comprueba si 'k' alcanzó el tamaño de 'T' y de nuevo verificamos si P(i) = T(k + i).
Como volvemos al inicio del bucle (se da por comprobado si el bucle finaliza), actualizamos la figura con el puntero en 'k', (k = 4) Ahora vemos que varias veces se cumple que P(i) = T(k + i), pero no tantas que se alcance el tamaño de 'P', y con cada coincidencia 'i' se ha incrementado, por lo que ahora 'i=6', pero se ha incrementado justo después de verificar si i = tamaño P luego devolver k (si no habríamos alcanzado la solución).
El algoritmo Knuth-Morris-Pratt (para este ejemplo) realiza 26 comparaciones hasta encontrar la solución, en la posición 15.
Es necesario recordar que al estar basado en array el índice es 0 (frente a la habitual forma de contar caracteres desde la posición 1), aunque por otra parte, en las figuras se ve cómo los punteros de 'k' e 'i' empiezan en 0.