dado un texto texto[0. . . N-1] y un patrón cama[0 . . . M-1] , escriba una función de búsqueda (char pat[], char txt[]) que imprima todas las apariciones de pat[] en txt[]. Puedes asumir que norte >M .

Ejemplos:

Aporte: txt[] = ESTE ES UN TEXTO DE PRUEBA, pat[] = PRUEBA
Producción: Patrón encontrado en el índice 10.

Aporte: txt[] = TUS PADRES
palmadita[] = AABA
Producción: Patrón encontrado en el índice 0, Patrón encontrado en el índice 9, Patrón encontrado en el índice 12

Llegadas de patrón en el texto.

Hemos discutido el algoritmo de búsqueda de patrones Naive en el Publicación anterior . El peor de los casos de complejidad del algoritmo Naive es O(m(n-m+1)). La complejidad temporal del algoritmo KMP es O (n+m) en el peor de los casos.

Búsqueda de patrones KMP (Knuth Morris Pratt):

El Algoritmo ingenuo de búsqueda de patrones no funciona bien en los casos en los que vemos muchos caracteres coincidentes seguidos de un carácter que no coincide.

Ejemplos:

1) txt[] = AAAAAAAAAAAAAAAAAAB, pat[] = AAAAB
2) txt[] = ABABABCABABABCABABABC, pat[] = ABABAC (no es el peor de los casos, pero sí un mal caso para Naive)

El algoritmo de coincidencia KMP utiliza la propiedad degenerativa (el patrón tiene los mismos subpatrones que aparecen más de una vez en el patrón) del patrón y mejora la complejidad del peor de los casos para O(n+metro) .

La idea básica detrás del algoritmo de KMP es: cada vez que detectamos una discrepancia (después de algunas coincidencias), ya conocemos algunos de los caracteres del texto de la siguiente ventana. Aprovechamos esta información para evitar que coincidan los caracteres que sabemos que coincidirán de todos modos.

Descripción general de coincidencias

txt = AAAAABAAABA
palmadita = AAAA
Comparamos la primera ventana de TXT con lo mismo

texto = AAAAA PADRE
incluso = AAAAA [Posición inicial]
Encontramos una coincidencia. Esto es lo mismo que Coincidencia de cadenas ingenua .

En el siguiente paso, comparamos la siguiente ventana de TXT con lo mismo .

texto = AAAAA DESTRUIR
incluso = AAAAA [El patrón cambió una posición]

Aquí es donde KMP optimiza sobre Naive. En esta segunda ventana, sólo comparamos la cuarta A del patrón.
con el cuarto carácter de la ventana de texto actual para decidir si la ventana actual coincide o no. ya que sabemos
Los primeros tres caracteres coincidirán de todos modos, nos saltamos la coincidencia de los primeros tres caracteres.

¿Necesidad de preprocesamiento?

De la explicación anterior surge una pregunta importante: cómo saber cuántos caracteres se deben omitir. Para saber esto,
preprocesamos el patrón y preparamos una matriz de números enteros lps[] que nos indica el recuento de caracteres que se omitirán

Descripción general del preprocesamiento:

• El algoritmo KMP preprocesa pat[] y construye un auxiliar lps[] de tamaño metro (igual que el tamaño del patrón) que se utiliza para omitir caracteres al hacer coincidir.
• Nombre lps indica el prefijo adecuado más largo que también es un sufijo. Un prefijo adecuado es un prefijo en el que no se permite una cadena completa. Por ejemplo, los prefijos de ABC son , A, AB y ABC. Los prefijos adecuados son , A y AB. Los sufijos de la cadena son, C, BC y ABC.
• Buscamos lps en subpatrones. Más claramente nos centramos en subcadenas de patrones que son tanto prefijos como sufijos.
• Para cada subpatrón pat[0..i] donde i = 0 a m-1, lps[i] almacena la longitud del prefijo adecuado máximo coincidente, que también es un sufijo del subpatrón pat[0..i] ].

lps[i] = el prefijo propio más largo de pat[0..i] que también es un sufijo de pat[0..i].

Nota: lps[i] también podría definirse como el prefijo más largo, que también es un sufijo adecuado. Necesitamos usarlo correctamente en un lugar para asegurarnos de que no se considere toda la subcadena.

Ejemplos de construcción lps[]:

Para el patrón AAAA, lps[] es [0, 1, 2, 3]

Para el patrón ABCDE, lps[] es [0, 0, 0, 0, 0]

Para el patrón AABAACAABAA, lps[] es [0, 1, 0, 1, 2, 0, 1, 2, 3, 4, 5]

Para el patrón AAACAAAAAC, lps[] es [0, 1, 2, 0, 1, 2, 3, 3, 3, 4]

Para el patrón AAABAAA, lps[] es [0, 1, 2, 0, 1, 2, 3]

Algoritmo de preprocesamiento:

En la parte de preprocesamiento,

• Calculamos valores en lps[] . Para hacer eso, realizamos un seguimiento de la longitud del valor de sufijo de prefijo más largo (usamos solo variable para este propósito) para el índice anterior
• Inicializamos lps[0] y solo como 0.
• Si palmadita[len] y camas coinciden, incrementamos solo en 1 y asigne el valor incrementado a lps[i].
• Si pat[i] y pat[len] no coinciden y len no es 0, actualizamos len a lps[len-1]
• Ver calcularLPSArray() en el siguiente código para más detalles

Ilustración de preprocesamiento (o construcción de lps[]):

palmadita[] = AAAAAAA

=> len = 0, yo = 0:

• lps[0] es siempre 0, nos movemos a i = 1

=> len = 0, yo = 1:

• Dado que pat[len] y pat[i] coinciden, haz len++,
• guárdelo en lps[i] y haga i++.
• Establecer len = 1, lps[1] = 1, i = 2

=> len = 1, yo = 2:

java reemplaza todo

• Dado que pat[len] y pat[i] coinciden, haz len++,
• guárdelo en lps[i] y haga i++.
• Establecer len = 2, lps[2] = 2, i = 3

=> len = 2, yo = 3:

• Dado que pat[len] y pat[i] no coinciden y len> 0,
• Establecer longitud = lps[len-1] = lps[1] = 1

=> len = 1, yo = 3:

• Dado que pat[len] y pat[i] no coinciden y len> 0,
• longitud = lps[len-1] = lps[0] = 0

=> len = 0, yo = 3:

• Dado que pat[len] y pat[i] no coinciden y len = 0,
• Establezca lps[3] = 0 y i = 4

=> len = 0, yo = 4:

• Dado que pat[len] y pat[i] coinciden, haz len++,
• Guárdelo en lps[i] y haga i++.
• Establecer len = 1, lps[4] = 1, i = 5

=> longitud = 1, yo = 5:

• Dado que pat[len] y pat[i] coinciden, haz len++,
• Guárdelo en lps[i] y haga i++.
• Establecer len = 2, lps[5] = 2, i = 6

=> len = 2, yo = 6:

• Dado que pat[len] y pat[i] coinciden, haz len++,
• Guárdelo en lps[i] y haga i++.
• longitud = 3, lps[6] = 3, yo = 7

=> len = 3, yo = 7:

• Dado que pat[len] y pat[i] no coinciden y len> 0,
• Establecer longitud = lps[len-1] = lps[2] = 2

=> len = 2, yo = 7:

• Dado que pat[len] y pat[i] coinciden, haz len++,
• Guárdelo en lps[i] y haga i++.
• longitud = 3, lps[7] = 3, yo = 8

Nos detenemos aquí ya que hemos construido los lps completos [].

Implementación del algoritmo KMP:

A diferencia del Algoritmo ingenuo , donde deslizamos el patrón uno y comparamos todos los caracteres en cada turno, usamos un valor de lps[] para decidir los siguientes caracteres que coincidirán. La idea es no coincidir con un personaje que sabemos que coincidirá de todos modos.

¿Cómo usar lps[] para decidir las siguientes posiciones (o saber el número de caracteres a omitir)?

• Comenzamos la comparación de pat[j] con j = 0 con caracteres de la ventana de texto actual.
• Seguimos haciendo coincidir los caracteres txt[i] y pat[j] y seguimos incrementando i y j mientras pat[j] y txt[i] mantienen pareo .
• Cuando vemos un discordancia
  • Sabemos que los caracteres pat[0..j-1] coinciden con txt[i-j…i-1] (tenga en cuenta que j comienza con 0 y lo incrementa solo cuando hay una coincidencia).
  • También sabemos (por la definición anterior) que lps[j-1] es el recuento de caracteres de pat[0…j-1] que son a la vez prefijo y sufijo adecuados.
  • De los dos puntos anteriores, podemos concluir que no necesitamos hacer coincidir estos caracteres lps[j-1] con txt[i-j…i-1] porque sabemos que estos caracteres coincidirán de todos modos. Consideremos el ejemplo anterior para entender esto.

A continuación se muestra la ilustración del algoritmo anterior:

Considere txt[] = AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA , palmadita[] = AAAAA

Si seguimos el proceso de construcción de LPS anterior, entonces lps[] = {0, 1, 2, 3}

-> yo = 0, j = 0: txt[i] y pat[j] coinciden, ¿i++, j++?

-> yo = 1, j = 1: txt[i] y pat[j] coinciden, ¿i++, j++?

-> yo = 2, j = 2: txt[i] y pat[j] coinciden, ¿i++, j++?

-> yo = 3, j = 3: txt[i] y pat[j] coinciden, ¿i++, j++?

-> yo = 4, j = 4: Dado que j = M, imprima el patrón encontrado y reinicie j, j = lps[j-1] = lps[3] = 3

Aquí, a diferencia del algoritmo Naive, no coincidimos con los tres primeros.
caracteres de esta ventana. El valor de lps[j-1] (en el paso anterior) nos dio el índice del siguiente carácter a coincidir.

-> yo = 4, j = 3: txt[i] y pat[j] coinciden, ¿i++, j++?

-> yo = 5, j = 4: Dado que j == M, imprima el patrón encontrado y reinicie j, j = lps[j-1] = lps[3] = 3
Nuevamente, a diferencia del algoritmo Naive, no hacemos coincidir los primeros tres caracteres de esta ventana. El valor de lps[j-1] (en el paso anterior) nos dio el índice del siguiente carácter a coincidir.

-> yo = 5, j = 3: txt[i] y pat[j] NO coinciden y j> 0, cambie solo j. j = lps[j-1] = lps[2] = 2

-> yo = 5, j = 2: txt[i] y pat[j] NO coinciden y j> 0, cambie solo j. j = lps[j-1] = lps[1] = 1

-> yo = 5, j = 1: txt[i] y pat[j] NO coinciden y j> 0, cambie solo j. j = lps[j-1] = lps[0] = 0

-> yo = 5, j = 0: txt[i] y pat[j] NO coinciden y j es 0, hacemos i++.

-> yo = 6, j = 0: txt[i] y pat[j] coinciden, ¿i++ y j++?

-> yo = 7, j = 1: txt[i] y pat[j] coinciden, ¿i++ y j++?

Continuamos de esta manera hasta que haya suficientes caracteres en el texto para compararlos con los caracteres del patrón…

A continuación se muestra la implementación del enfoque anterior:

C++

>

>

Java

>

>

Python3

>

>

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)) { si ($pat[$j] == $txt[$i]) { $j++;  $yo++;  } if ($j == $M) { printf('Patrón encontrado en el índice '.($i - $j));  $j = $lps[$j - 1];  } // no coincide después de j coincide con else if ($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 ?>>
 
 
 
 
    
 
>
 
    
 
>
 
  Producción  
 
Found pattern at index 10>
 
    Complejidad del tiempo:    O(N+M) donde N es la longitud del texto y M es la longitud del patrón que se va a encontrar.  
    Espacio Auxiliar:    O(M)