Donat un text txt[0 . . . N-1] i un patró llit[0 . . . M-1] , escriviu una funció de cerca (char pat[], char txt[]) que imprimeixi totes les ocurrències de pat[] a txt[]. Això ho pots suposar N > M .

Exemples:

Entrada: txt[] = AQUEST ÉS UN TEXT DE PROVA, pat[] = PROVA
Sortida: Patró trobat a l'índex 10

Entrada: txt[] = ELS VOSTRE PARE
pat[] = AABA
Sortida: Patró trobat a l'índex 0, Patró trobat a l'índex 9, Patró trobat a l'índex 12

Arribades de patró al text

Hem parlat de l'algoritme de cerca de patrons naïf al publicació anterior . La complexitat del pitjor cas de l'algorisme Naive és O(m(n-m+1)). La complexitat temporal de l'algorisme KMP és O(n+m) en el pitjor dels casos.

Cerca de patró KMP (Knuth Morris Pratt):

El Algorisme ingenu de cerca de patrons no funciona bé en els casos en què veiem molts caràcters coincidents seguits d'un caràcter que no coincideix.

Exemples:

1) txt[] = AAAAAAAAAAAAAAAAAAB, pat[] = AAAAB
2) txt[] = ABABABCABABABCABABABC, pat[] = ABABAC (no és el pitjor dels casos, però és un mal cas per a Naive)

L'algoritme de concordança KMP utilitza la propietat degenerativa (patró que té els mateixos sub-patrons que apareixen més d'una vegada al patró) del patró i millora la complexitat del pitjor dels casos per O(n+m) .

La idea bàsica darrere de l'algorisme de KMP és: sempre que detectem un desajust (després d'algunes coincidències), ja coneixem alguns dels caràcters del text de la finestra següent. Aprofitem aquesta informació per evitar fer coincidir els personatges que sabem que coincidiran de totes maneres.

Visió general de la concordança

txt = AAAAABAAABA
pat = AAAA
Comparem la primera finestra de txt amb el mateix

txt = AAAA PARE
fins i tot = AAAA [Posició inicial]
Trobem un partit. Això és el mateix que Coincidència de cordes ingènua .

En el següent pas, comparem la següent finestra de txt amb el mateix .

txt = AAAAA DESTRUIR
fins i tot = AAAA [El patró ha canviat una posició]

Aquí és on KMP fa l'optimització sobre Naive. En aquesta segona finestra, només comparem la quarta A del patró
amb el quart caràcter de la finestra actual de text per decidir si la finestra actual coincideix o no. Des que ho sabem
Els tres primers caràcters coincidiran de totes maneres, hem omès fer coincidir els tres primers caràcters.

Necessitat de preprocessament?

Una pregunta important sorgeix de l'explicació anterior, com saber quants caràcters s'han de saltar. Per saber això,
preprocessem el patró i preparem una matriu d'enters lps[] que ens indica el recompte de caràcters que cal saltar

Visió general del preprocessament:

• L'algorisme KMP preprocessa pat[] i construeix un auxiliar lps[] de mida m (igual que la mida del patró) que s'utilitza per saltar caràcters mentre coincideixen.
• Nom lps indica el prefix propi més llarg que també és un sufix. Un prefix adequat és un prefix amb una cadena sencera no permesa. Per exemple, els prefixos d'ABC són , A, AB i ABC. Els prefixos propis són , A i AB. Els sufixos de la cadena són , C, BC i ABC.
• Busquem lps en subpatrons. Més clarament ens centrem en les subcadenes de patrons que són alhora prefix i sufix.
• Per a cada sub-patró pat[0..i] on i = 0 a m-1, lps[i] emmagatzema la longitud del prefix adequat màxim coincident que també és un sufix del sub-patró pat[0..i ].

lps[i] = el prefix propi més llarg de pat[0..i] que també és un sufix de pat[0..i].

Nota: lps[i] també es podria definir com el prefix més llarg que també és un sufix propi. Hem d'utilitzar-lo correctament en un sol lloc per assegurar-nos que no es té en compte tota la subcadena.

Exemples de construcció de lps[]:

Per al patró AAAA, lps[] és [0, 1, 2, 3]

Per al patró ABCDE, lps[] és [0, 0, 0, 0, 0]

Per al patró AABAACAABAA, lps[] és [0, 1, 0, 1, 2, 0, 1, 2, 3, 4, 5]

Per al patró AAAACAAAAAC, lps[] és [0, 1, 2, 0, 1, 2, 3, 3, 3, 4]

Per al patró AAABAAA, lps[] és [0, 1, 2, 0, 1, 2, 3]

Algorisme de preprocessament:

A la part de preprocessament,

• Calculem valors en lps[] . Per fer-ho, fem un seguiment de la longitud del valor de sufix de prefix més llarg (utilitzem només variable per a aquesta finalitat) per a l'índex anterior
• Inicialitzem lps[0] i només com 0.
• Si pat[len] i llits coincideixen, augmentem només per 1 i assigneu el valor incrementat a lps[i].
• Si pat[i] i pat[len] no coincideixen i len no és 0, actualitzem len a lps[len-1]
• Vegeu computeLPSArray() al codi següent per obtenir més informació

Il·lustració del preprocessament (o construcció de lps[]):

pat[] = AAAAAAA

=> len = 0, i = 0:

• lps[0] sempre és 0, passem a i = 1

=> len = 0, i = 1:

• Com que pat[len] i pat[i] coincideixen, feu len++,
• emmagatzemar-lo a lps[i] i fer i++.
• Estableix len = 1, lps[1] = 1, i = 2

=> len = 1, i = 2:

• Com que pat[len] i pat[i] coincideixen, feu len++,
• emmagatzemar-lo a lps[i] i fer i++.
• Estableix len = 2, lps[2] = 2, i = 3

=> len = 2, i = 3:

• Com que pat[len] i pat[i] no coincideixen, i len> 0,
• Estableix len = lps[len-1] = lps[1] = 1

=> len = 1, i = 3:

• Com que pat[len] i pat[i] no coincideixen i len> 0,
• len = lps[len-1] = lps[0] = 0

=> len = 0, i = 3:

• Com que pat[len] i pat[i] no coincideixen i len = 0,
• Estableix lps[3] = 0 i i = 4

=> len = 0, i = 4:

• Com que pat[len] i pat[i] coincideixen, feu len++,
• Emmagatzemeu-lo a lps[i] i feu i++.
• Estableix len = 1, lps[4] = 1, i = 5

=> len = 1, i = 5:

• Com que pat[len] i pat[i] coincideixen, feu len++,
• Emmagatzemeu-lo a lps[i] i feu i++.
• Estableix len = 2, lps[5] = 2, i = 6

=> len = 2, i = 6:

• Com que pat[len] i pat[i] coincideixen, feu len++,
• Emmagatzemeu-lo a lps[i] i feu i++.
• len = 3, lps[6] = 3, i = 7

=> len = 3, i = 7:

• Com que pat[len] i pat[i] no coincideixen i len> 0,
• Estableix len = lps[len-1] = lps[2] = 2

=> len = 2, i = 7:

• Com que pat[len] i pat[i] coincideixen, feu len++,
• Emmagatzemeu-lo a lps[i] i feu i++.
• len = 3, lps[7] = 3, i = 8

Ens aturem aquí, ja que hem construït tot el lps[].

Implementació de l'algorisme KMP:

A diferència del Algorisme ingenu , on fem lliscar el patró per un i comparem tots els caràcters a cada torn, fem servir un valor de lps[] per decidir els següents caràcters que s'han de fer coincidir. La idea és no coincidir amb un personatge que sabem que coincidirà de totes maneres.

Com utilitzar lps[] per decidir les properes posicions (o per saber el nombre de caràcters que cal saltar)?

• Comencem la comparació de pat[j] amb j = 0 amb caràcters de la finestra de text actual.
• Seguim fent coincidir els caràcters txt[i] i pat[j] i seguim incrementant i i j mentre que pat[j] i txt[i] mantenen coincidència .
• Quan veiem a desajustament
  • Sabem que els caràcters pat[0..j-1] coincideixen amb txt[i-j...i-1] (Tingueu en compte que j comença amb 0 i l'incrementa només quan hi ha una coincidència).
  • També sabem (per la definició anterior) que lps[j-1] és el recompte de caràcters de pat[0...j-1] que són alhora prefix i sufix propis.
  • A partir dels dos punts anteriors, podem concloure que no hem de fer coincidir aquests caràcters lps[j-1] amb txt[i-j...i-1] perquè sabem que aquests caràcters coincidiran de totes maneres. Considerem l'exemple anterior per entendre-ho.

A continuació es mostra la il·lustració de l'algorisme anterior:

Considereu txt[] = AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA , pat[] = AAAA

Si seguim el procés de construcció de LPS anterior, aleshores lps[] = {0, 1, 2, 3}

-> i = 0, j = 0: txt[i] i pat[j] coincideixen, fer i++, j++

-> i = 1, j = 1: txt[i] i pat[j] coincideixen, fer i++, j++

-> i = 2, j = 2: txt[i] i pat[j] coincideixen, fer i++, j++

-> i = 3, j = 3: txt[i] i pat[j] coincideixen, fer i++, j++

-> i = 4, j = 4: Com que j = M, s'ha trobat el patró d'impressió i es reinicia j, j = lps[j-1] = lps[3] = 3

Aquí, a diferència de l'algorisme Naive, no coincideixen amb els tres primers
personatges d'aquesta finestra. El valor de lps[j-1] (al pas anterior) ens va donar l'índex del caràcter següent per coincidir.

-> i = 4, j = 3: txt[i] i pat[j] coincideixen, fer i++, j++

-> i = 5, j = 4: Com que j == M, s'ha trobat el patró d'impressió i s'ha restablert j, j = lps[j-1] = lps[3] = 3
De nou, a diferència de l'algorisme Naive, no coincideixen els tres primers caràcters d'aquesta finestra. El valor de lps[j-1] (al pas anterior) ens va donar l'índex del caràcter següent per coincidir.

-> i = 5, j = 3: txt[i] i pat[j] NO coincideixen i j> 0, canvieu només j. j = lps[j-1] = lps[2] = 2

-> i = 5, j = 2: txt[i] i pat[j] NO coincideixen i j> 0, canvia només j. j = lps[j-1] = lps[1] = 1

-> i = 5, j = 1: txt[i] i pat[j] NO coincideixen i j> 0, canvieu només j. j = lps[j-1] = lps[0] = 0

-> i = 5, j = 0: txt[i] i pat[j] NO coincideixen i j és 0, fem i++.

-> i = 6, j = 0: txt[i] i pat[j] coincideixen, fes i++ i j++

-> i = 7, j = 1: txt[i] i pat[j] coincideixen, fes i++ i j++

Continuem així fins que hi hagi prou caràcters al text per comparar-los amb els caràcters del patró...

A continuació es mostra la implementació de l'enfocament anterior:

C++

>

>

Java

>

>

Python 3

>

>

C#

>

>

Javascript

> 
    
   
 
     
  
 
    
 
     
     
    
 
 
 
 
 
  // PHP program for implementation of KMP pattern searching // algorithm // Prints occurrences of txt[] in pat[] function KMPSearch($pat, $txt) {  $M = strlen($pat);  $N = strlen($txt);  // create lps[] that will hold the longest prefix suffix  // values for pattern  $lps=array_fill(0,$M,0);  // Preprocess the pattern (calculate lps[] array)  computeLPSArray($pat, $M, $lps);  $i = 0; // index for txt[]  $j = 0; // index for pat[]  while (($N - $i)>= ($M - $j)) { if ($pat[$j] == $txt[$i]) { $j++;  $i++;  } if ($j == $M) { printf('Patró trobat a l'índex '.($i - $j));  $j = $lps[$j - 1];  } // No coincideix després que j coincideixi si no ($i<$N && $pat[$j] != $txt[$i]) {  // Do not match lps[0..lps[j-1]] characters,  // they will match anyway  if ($j != 0)  $j = $lps[$j - 1];  else  $i = $i + 1;  }  } } // Fills lps[] for given pattern pat[0..M-1] function computeLPSArray($pat, $M, &$lps) {  // Length of the previous longest prefix suffix  $len = 0;  $lps[0] = 0; // lps[0] is always 0  // The loop calculates lps[i] for i = 1 to M-1  $i = 1;  while ($i <$M) {  if ($pat[$i] == $pat[$len]) {  $len++;  $lps[$i] = $len;  $i++;  }  else // (pat[i] != pat[len])  {  // This is tricky. Consider the example.  // AAACAAAA and i = 7. The idea is similar  // to search step.  if ($len != 0) {  $len = $lps[$len - 1];  // Also, note that we do not increment  // i here  }  else // if (len == 0)  {  $lps[$i] = 0;  $i++;  }  }  } } // Driver program to test above function  $txt = 'ABABDABACDABABCABAB';  $pat = 'ABABCABAB';  KMPSearch($pat, $txt);   // This code is contributed by chandan_jnu ?>>
 
 
 
 
    
 
>
 
    
 
>
 
  Sortida  
 
Found pattern at index 10>
 
    Complexitat temporal:    O(N+M) on N és la longitud del text i M és la longitud del patró a trobar.  
    Espai auxiliar:    O(M)
un milió en xifres