Algoritme Knuth-Morris-Pratt

L'algoritme KMP és un algoritme de busca de subcadena simple. Per lo tant el seu objectiu és buscar l'existència d'una subcadena (habitualment cridada patró) dins d'una atra cadena. La busca es porta a terme utilisant informació basada en els fallos previs. Informació obtinguda del propi patró creant prèviament una taula de valors sobre el seu propi contingut. L'objectiu de crear dita taula és poder determinar a on podria donar-se la següent existència, sense necessitat d'analisar més d'1 volta els caràcters de la cadena a on es busca.

En 1970 S.A. Cook va sugerir l'existència d'un algoritme que resol la busca en un temps equivalent a M+N, en el pijor cas, a raïl d'uns resultats teòrics que va obtindre mentres provava un tipo de màquina abstracta. Knuth i Pratt seguint els passos que Cook va usar per a provar la seua teorema, varen conseguir crear l'algoritme que du els seus noms. De modo independent Morris mentres treballava en un editor de text va acabar descobrint el mateix algoritme, per a satisfer la qüestió de la busca eficient de subcadena, i que varen publicar junts els tres en 1976.

Descripció de l'algoritme KMP

L'algoritme KMP tracta de localisar la posició de començ d'una cadena dins d'una atra. Prèviament sobre el patró a localisar es calcula una taula de bots (coneguda com a taula de fallos) que despuix s'utilisa (en examinar les cadenes) per a fer bots quan es localisa un fallo de coincidència en la comparació d'un caràcter.

Supongam una taula 'F' ya precalculada, i supongam que el patró a buscar estiga contingut en la matriu 'P()', i la cadena a on busquem estiga continguda en la matriu 'T()'. Llavors abdós cadenes comencen a comparar-se usant una busca d'alvanç per al patró, si ocorre un fallo (de coincidència), la busca bota cap a on indica el valor en la posició de la busca actual sobre la taula de fallos. El array 'T' utilisa una busca d'alvanç absolut que determina el començ d'una secció del mateix tamany que el patró. Dins de dita secció es desplaça en la busca del patró, analisant cada caràcter en la secció en cada caràcter en el patró. Es donen 2 situacions:

Mentres existixquen coincidències la busca d'alvanç de 'P', es va incrementant (apunta al següent parell de caràcters a comparar entre el patró i la secció actual en el array 'T') i si alcança el final del patró es torna la posició actual de la busca absoluta de l'array 'T'.

Si es dona un fallo, la secció de l'array 'T' (la busca absoluta d'alvanç) s'actualisa, sumant el valor de la busca de 'P' + el valor que conté la taula 'F' en el mateix índex que 'P'. Ademés d'actualisar la secció baix examen, deu igualment alinear-se el patró baix dita secció, per a coincidir baix una de 2 circumstàncies; Si el valor de 'F' és major que -1 la busca de 'P', pren el valor que indica la taula de bot 'F', en cas contrari torna a recomenzar el seu valor en 0 (començ del patró i de la següent secció).

Pseudocódigo de l'algoritme

En el pseudocódigo no s'inclou la verificació de les cadenes buides.

 Algoritme BúsquedaKMP:
 Entrada:
   un array de caràcters, T  (el text a on es busca)
   un array de caràcters,  P (la paraula/s (patró) que es busca)
 Eixida:
   un sancer                  (que expressa la posició en T en la qual es va trobar P) 

 Variables en joc:
   un sancer, k ← 0           (posició absoluta de la secció baix examen en el array T)
   un sancer, i ← 0           (posició absoluta del caràcter baix examen en el array P)
   un sancer, m ← size(T)     (Cantitat de caràcters en el array T)
   un sancer, n ← size(P)     (cantitat de caràcters en el array P)     
   un array de sancers, F     (la taula de fallo, calculada prèviament o a continuació)
       
 Còdic:
   Si (m => n)
     F = TablaKMP(P)          (calcula la taula de fallos)

En Bucle Mentres ((i < n) i ((k + i) < m) )

       Si P[i] = T[k + i]        
         Assignar i ← (i + 1)
       Si no 
         Assignar k ← (k + i - F[i])
         Si (i > 0) Assignar i ← F[i]
       Fi si
     Repetir
   Fi si
           
   Si (i = n) 
     Tornar k
   si no
     Tornar m               (o tornar -1, si s'usa un sancer en signe)
   Fi si