algorithm
Búsqueda de subcadena
Buscar..
Algoritmo KMP en C
Dado un texto txt y un patrón pat , el objetivo de este programa será imprimir toda la ocurrencia de pat en txt .
Ejemplos:
Entrada:
txt[] = "THIS IS A TEST TEXT"
pat[] = "TEST"
salida:
Pattern found at index 10
Entrada:
txt[] = "AABAACAADAABAAABAA"
pat[] = "AABA"
salida:
Pattern found at index 0
Pattern found at index 9
Pattern found at index 13
Implementación del lenguaje C:
// C program for implementation of KMP pattern searching
// algorithm
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
void computeLPSArray(char *pat, int M, int *lps);
void KMPSearch(char *pat, char *txt)
{
int M = strlen(pat);
int N = strlen(txt);
// create lps[] that will hold the longest prefix suffix
// values for pattern
int *lps = (int *)malloc(sizeof(int)*M);
int j = 0; // index for pat[]
// Preprocess the pattern (calculate lps[] array)
computeLPSArray(pat, M, lps);
int i = 0; // index for txt[]
while (i < N)
{
if (pat[j] == txt[i])
{
j++;
i++;
}
if (j == M)
{
printf("Found pattern at index %d \n", i-j);
j = lps[j-1];
}
// mismatch after j matches
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;
}
}
free(lps); // to avoid memory leak
}
void computeLPSArray(char *pat, int M, int *lps)
{
int len = 0; // length of the previous longest prefix suffix
int i;
lps[0] = 0; // lps[0] is always 0
i = 1;
// the loop calculates lps[i] for i = 1 to M-1
while (i < M)
{
if (pat[i] == pat[len])
{
len++;
lps[i] = len;
i++;
}
else // (pat[i] != pat[len])
{
if (len != 0)
{
// This is tricky. Consider the example
// AAACAAAA and i = 7.
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
int main()
{
char *txt = "ABABDABACDABABCABAB";
char *pat = "ABABCABAB";
KMPSearch(pat, txt);
return 0;
}
Salida:
Found pattern at index 10
Referencia:
http://www.geeksforgeeks.org/searching-for-patterns-set-2-kmp-algorithm/
Introducción al algoritmo de Rabin-Karp
El algoritmo de Rabin-Karp es un algoritmo de búsqueda de cadenas creado por Richard M. Karp y Michael O. Rabin que utiliza el hash para encontrar cualquiera de un conjunto de cadenas de patrones en un texto.
Una subcadena de una cadena es otra cadena que aparece en. Por ejemplo, ver es una subcadena de stackoverflow . No debe confundirse con la subsecuencia porque cover es una subsecuencia de la misma cadena. En otras palabras, cualquier subconjunto de letras consecutivas en una cadena es una subcadena de la cadena dada.
En el algoritmo de Rabin-Karp, generaremos un hash de nuestro patrón que estamos buscando y verificaremos si el hash de nuestro texto coincide con el patrón o no. Si no coincide, podemos garantizar que el patrón no existe en el texto . Sin embargo, si coincide, el patrón puede estar presente en el texto . Veamos un ejemplo:
Digamos que tenemos un texto: yeminsajid y queremos averiguar si el patrón nsa existe en el texto. Para calcular el hash y el hash rodante, necesitaremos usar un número primo. Este puede ser cualquier número primo. Tomemos prime = 11 para este ejemplo. Determinaremos el valor de hash usando esta fórmula:
(1st letter) X (prime) + (2nd letter) X (prime)¹ + (3rd letter) X (prime)² X + ......
Vamos a denotar:
a -> 1 g -> 7 m -> 13 s -> 19 y -> 25
b -> 2 h -> 8 n -> 14 t -> 20 z -> 26
c -> 3 i -> 9 o -> 15 u -> 21
d -> 4 j -> 10 p -> 16 v -> 22
e -> 5 k -> 11 q -> 17 w -> 23
f -> 6 l -> 12 r -> 18 x -> 24
El valor de hash de nsa será:
14 X 11⁰ + 19 X 11¹ + 1 X 11² = 344
Ahora encontramos el hash de nuestro texto. Si el hash variable coincide con el valor de hash de nuestro patrón, verificaremos si las cadenas coinciden o no. Ya que nuestro patrón tiene 3 letras, tomaremos las primeras 3 letras yem de nuestro texto y calcularemos el valor de hash. Obtenemos:
25 X 11⁰ + 5 X 11¹ + 13 X 11² = 1653
Este valor no coincide con el valor hash de nuestro patrón. Así que la cadena no existe aquí. Ahora tenemos que considerar el siguiente paso. Para calcular el valor hash de nuestra siguiente cadena emi . Podemos calcular esto utilizando nuestra fórmula. Pero eso sería bastante trivial y nos costaría más. En su lugar, utilizamos otra técnica.
- Restamos el valor de la Primera letra de la cadena anterior de nuestro valor de hash actual. En este caso, y . Obtenemos,
1653 - 25 = 1628. - Dividimos la diferencia con nuestro principal , que es 11 para este ejemplo. Lo obtenemos,
1628 / 11 = 148. - Añadimos la nueva letra X (primo) ᵐ⁻¹ , donde m es la longitud del patrón, con el cociente, que es i = 9 . Obtenemos,
148 + 9 X 11² = 1237.
El nuevo valor de hash no es igual a nuestro valor de hash de patrones. Continuando, para n obtenemos:
Previous String: emi
First Letter of Previous String: e(5)
New Letter: n(14)
New String: "min"
1237 - 5 = 1232
1232 / 11 = 112
112 + 14 X 11² = 1806
No coincide. Después de eso, por s , obtenemos:
Previous String: min
First Letter of Previous String: m(13)
New Letter: s(19)
New String: "ins"
1806 - 13 = 1793
1793 / 11 = 163
163 + 19 X 11² = 2462
No coincide. A continuación, para a , obtenemos:
Previous String: ins
First Letter of Previous String: i(9)
New Letter: a(1)
New String: "nsa"
2462 - 9 = 2453
2453 / 11 = 223
223 + 1 X 11² = 344
¡Es un partido! Ahora comparamos nuestro patrón con la cadena actual. Como ambas cadenas coinciden, la subcadena existe en esta cadena. Y volvemos a la posición inicial de nuestra subcadena.
El pseudocódigo será:
Cálculo de hash:
Procedure Calculate-Hash(String, Prime, x):
hash := 0 // Here x denotes the length to be considered
for m from 1 to x // to find the hash value
hash := hash + (Value of String[m])ᵐ⁻¹
end for
Return hash
Recálculo de hash:
Procedure Recalculate-Hash(String, Curr, Prime, Hash):
Hash := Hash - Value of String[Curr] //here Curr denotes First Letter of Previous String
Hash := Hash / Prime
m := String.length
New := Curr + m - 1
Hash := Hash + (Value of String[New])ᵐ⁻¹
Return Hash
Partido de cuerda
Procedure String-Match(Text, Pattern, m):
for i from m to Pattern-length + m - 1
if Text[i] is not equal to Pattern[i]
Return false
end if
end for
Return true
Rabin-Karp:
Procedure Rabin-Karp(Text, Pattern, Prime):
m := Pattern.Length
HashValue := Calculate-Hash(Pattern, Prime, m)
CurrValue := Calculate-Hash(Pattern, Prime, m)
for i from 1 to Text.length - m
if HashValue == CurrValue and String-Match(Text, Pattern, i) is true
Return i
end if
CurrValue := Recalculate-Hash(String, i+1, Prime, CurrValue)
end for
Return -1
Si el algoritmo no encuentra ninguna coincidencia, simplemente devuelve -1 .
Este algoritmo se utiliza en la detección de plagio. Dado el material de origen, el algoritmo puede buscar rápidamente en un papel ejemplos de oraciones del material de origen, ignorando detalles como el caso y la puntuación. Debido a la abundancia de las cadenas buscadas, los algoritmos de búsqueda de una sola cadena no son prácticos aquí. De nuevo, el algoritmo Knuth-Morris-Pratt o el algoritmo de búsqueda de cadenas de Boyer-Moore es un algoritmo de búsqueda de cadenas de un solo patrón más rápido que Rabin-Karp . Sin embargo, es un algoritmo de elección para la búsqueda de múltiples patrones. Si queremos encontrar alguno de los números grandes, digamos k, patrones de longitud fija en un texto, podemos crear una variante simple del algoritmo de Rabin-Karp.
Para el texto de longitud N y P patrones de longitud combinada m, su promedio y mejor de los casos tiempo de ejecución es O (n + m) en O espacio (p), pero su tiempo del peor caso es O (nm).
Introducción al algoritmo de Knuth-Morris-Pratt (KMP)
Supongamos que tenemos un texto y un patrón . Necesitamos determinar si el patrón existe en el texto o no. Por ejemplo:
+-------+---+---+---+---+---+---+---+---+
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
+-------+---+---+---+---+---+---+---+---+
| Text | a | b | c | b | c | g | l | x |
+-------+---+---+---+---+---+---+---+---+
+---------+---+---+---+---+
| Index | 0 | 1 | 2 | 3 |
+---------+---+---+---+---+
| Pattern | b | c | g | l |
+---------+---+---+---+---+
Este patrón existe en el texto . Por lo tanto, nuestra búsqueda de subcadenas debe devolver 3 , el índice de la posición a partir de la cual comienza este patrón . Entonces, ¿cómo funciona nuestro procedimiento de búsqueda de subcadenas de fuerza bruta?
Lo que normalmente hacemos es: comenzamos desde el índice 0 del texto y el índice 0 de nuestro patrón * y comparamos el Texto [0] con el Patrón [0] . Como no coinciden, pasamos al siguiente índice de nuestro texto y comparamos el Texto [1] con el Patrón [0] . Como se trata de una coincidencia, incrementamos el índice de nuestro patrón y el índice del Texto también. Comparamos el texto [2] con el patrón [1] . También son un partido. Siguiendo el mismo procedimiento establecido anteriormente, ahora comparamos el Texto [3] con el Patrón [2] . Como no coinciden, comenzamos desde la siguiente posición donde comenzamos a encontrar el partido. Ese es el índice 2 del texto . Comparamos el texto [2] con el patrón [0] . Ellos no coinciden. Luego, incrementando el índice del texto , comparamos el texto [3] con el patrón [0] . Ellos coinciden. Nuevamente coinciden el texto [4] y el patrón [1] , coinciden el texto [5] y el patrón [2] y coinciden el texto [6] y el patrón [3] . Desde que llegamos al final de nuestro patrón , ahora devolvemos el índice desde el que comenzó nuestra coincidencia, que es 3 . Si nuestro patrón era: bcgll , eso significa que si el patrón no existía en nuestro texto , nuestra búsqueda debería devolver una excepción o -1 o cualquier otro valor predefinido. Podemos ver claramente que, en el peor de los casos, este algoritmo tomaría O(mn) tiempo donde m es la longitud del Texto yn es la longitud del Patrón . ¿Cómo reducimos esta complejidad del tiempo? Aquí es donde KMP Substring Search Algorithm entra en la imagen.
El Algoritmo de Búsqueda de Cadenas Knuth-Morris-Pratt o el Algoritmo KMP busca las ocurrencias de un "Patrón" dentro de un "Texto" principal mediante el uso de la observación de que cuando se produce una falta de coincidencia, la palabra en sí incluye información suficiente para determinar dónde podría comenzar la próxima coincidencia , evitando así el reexamen de personajes previamente emparejados. El algoritmo fue concebido en 1970 por Donuld Knuth y Vaughan Pratt e independientemente por James H. Morris . El trío lo publicó conjuntamente en 1977.
Extendamos nuestro ejemplo Texto y patrón para una mejor comprensión:
+-------+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| Index |0 |1 |2 |3 |4 |5 |6 |7 |8 |9 |10|11|12|13|14|15|16|17|18|19|20|21|22|
+-------+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| Text |a |b |c |x |a |b |c |d |a |b |x |a |b |c |d |a |b |c |d |a |b |c |y |
+-------+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
+---------+---+---+---+---+---+---+---+---+
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
+---------+---+---+---+---+---+---+---+---+
| Pattern | a | b | c | d | a | b | c | y |
+---------+---+---+---+---+---+---+---+---+
Al principio, nuestro texto y patrón coinciden hasta el índice 2 . El texto [3] y el patrón [3] no coinciden. Por lo tanto, nuestro objetivo es no retroceder en este Texto , es decir, en caso de una falta de coincidencia, no queremos que nuestra coincidencia comience nuevamente desde la posición con la que comenzamos a coincidir. Para lograrlo, buscaremos un sufijo en nuestro patrón justo antes de que se produzca la discrepancia (subcadena abc ), que también es un prefijo de la subcadena de nuestro patrón . Para nuestro ejemplo, ya que todos los caracteres son únicos, no hay sufijo, es el prefijo de nuestra subcadena coincidente. Entonces, lo que eso significa es que nuestra próxima comparación comenzará a partir del índice 0 . Espera un momento, entenderás por qué hicimos esto. A continuación, comparamos el Texto [3] con el Patrón [0] y no coincide. Después de eso, para el texto del índice 4 al índice 9 y para el patrón del índice 0 al índice 5 , encontramos una coincidencia. Encontramos una falta de coincidencia en Texto [10] y Patrón [6] . Así que tomamos la subcadena del patrón justo antes del punto donde se produce la discrepancia (subcadena abcdabc ), verificamos si hay un sufijo, que también es un prefijo de esta subcadena. Podemos ver aquí que ab es tanto el sufijo como el prefijo de esta subcadena. Lo que eso significa es que, desde que hemos hecho coincidir hasta Texto [10] , los caracteres justo antes de la falta de coincidencia son ab . Lo que podemos inferir de esto es que dado que ab también es un prefijo de la subcadena que tomamos, no tenemos que marcar ab nuevamente y la próxima verificación puede comenzar desde Texto [10] y Patrón [2] . No tuvimos que volver a mirar el texto completo, podemos comenzar directamente desde donde ocurrió nuestra falta de coincidencia. Ahora verificamos Texto [10] y Patrón [2] , ya que es una falta de coincidencia, y la subcadena antes de la falta de coincidencia ( abc ) no contiene un sufijo que también es un prefijo, verificamos Texto [10] y Patrón [0] , no coinciden Después, para Texto del índice 11 al índice 17 y para Patrón del índice 0 al índice 6 . Encontramos una falta de coincidencia en Texto [18] y Patrón [7] . De nuevo, comprobamos la subcadena antes de la discrepancia (subcadena abcdabc ) y encontramos que abc es tanto el sufijo como el prefijo. Entonces, ya que hemos emparejado hasta el Patrón [7] , abc debe estar antes del Texto [18] . Eso significa que no necesitamos comparar hasta Texto [17] y nuestra comparación comenzará a partir de Texto [18] y Patrón [3] . Por lo tanto, encontraremos una coincidencia y devolveremos 15, que es nuestro índice de inicio de la partida. Así es como funciona nuestra búsqueda de subcadenas KMP usando la información de sufijo y prefijo.
Ahora, ¿cómo calculamos de manera eficiente si el sufijo es igual al prefijo y en qué punto comenzar la comprobación si hay una falta de correspondencia de caracteres entre el texto y el patrón ? Echemos un vistazo a un ejemplo:
+---------+---+---+---+---+---+---+---+---+
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
+---------+---+---+---+---+---+---+---+---+
| Pattern | a | b | c | d | a | b | c | a |
+---------+---+---+---+---+---+---+---+---+
Generaremos una matriz que contenga la información requerida. Llamemos a la matriz S. El tamaño de la matriz será igual a la longitud del patrón. Como la primera letra del patrón no puede ser el sufijo de ningún prefijo, pondremos S [0] = 0 . Tomamos i = 1 y j = 0 al principio. En cada paso, comparamos el Patrón [i] y el Patrón [j] y el incremento i . Si hay una coincidencia, ponemos S [i] = j + 1 e incrementamos j , si hay una discrepancia, verificamos la posición del valor anterior de j (si está disponible) y establecemos j = S [j-1] (si j no es igual a 0 ), seguimos haciendo esto hasta que S [j] no coincida con S [i] o j no se convierta en 0 . Para el último, ponemos S [i] = 0 . Para nuestro ejemplo:
j i
+---------+---+---+---+---+---+---+---+---+
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
+---------+---+---+---+---+---+---+---+---+
| Pattern | a | b | c | d | a | b | c | a |
+---------+---+---+---+---+---+---+---+---+
El patrón [j] y el patrón [i] no coinciden, por lo que incrementamos i y como j es 0 , no verificamos el valor anterior y colocamos el patrón [i] = 0 . Si seguimos incrementando i , para i = 4 , obtendremos una coincidencia, por lo que colocamos S [i] = S [4] = j + 1 = 0 + 1 = 1 e incrementamos j e i . Nuestra matriz se verá como:
j i
+---------+---+---+---+---+---+---+---+---+
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
+---------+---+---+---+---+---+---+---+---+
| Pattern | a | b | c | d | a | b | c | a |
+---------+---+---+---+---+---+---+---+---+
| S | 0 | 0 | 0 | 0 | 1 | | | |
+---------+---+---+---+---+---+---+---+---+
Como el Patrón [1] y el Patrón [5] son una coincidencia, ponemos S [i] = S [5] = j + 1 = 1 + 1 = 2 . Si continuamos, encontraremos una falta de coincidencia para j = 3 yi = 7 . Como j no es igual a 0 , ponemos j = S [j-1] . Y compararemos los caracteres en i y j son iguales o no, ya que son iguales, pondremos S [i] = j + 1. Nuestra matriz completa se verá así:
+---------+---+---+---+---+---+---+---+---+
| S | 0 | 0 | 0 | 0 | 1 | 2 | 3 | 1 |
+---------+---+---+---+---+---+---+---+---+
Esta es nuestra matriz requerida. Aquí, un valor distinto de cero de S [i] significa que hay un sufijo de longitud S [i] igual al prefijo en esa subcadena (subcadena de 0 a i ) y la próxima comparación comenzará desde la posición S [i] + 1 del Patrón Nuestro algoritmo para generar la matriz se vería así:
Procedure GenerateSuffixArray(Pattern):
i := 1
j := 0
n := Pattern.length
while i is less than n
if Pattern[i] is equal to Pattern[j]
S[i] := j + 1
j := j + 1
i := i + 1
else
if j is not equal to 0
j := S[j-1]
else
S[i] := 0
i := i + 1
end if
end if
end while
La complejidad del tiempo para construir esta matriz es O(n) y la complejidad del espacio también es O(n) . Para asegurarse de que ha entendido completamente el algoritmo, intente generar una matriz para el patrón aabaabaa y verifique si el resultado coincide con este .
Ahora hagamos una búsqueda de subcadenas usando el siguiente ejemplo:
+---------+---+---+---+---+---+---+---+---+---+---+---+---+
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |10 |11 |
+---------+---+---+---+---+---+---+---+---+---+---+---+---+
| Text | a | b | x | a | b | c | a | b | c | a | b | y |
+---------+---+---+---+---+---+---+---+---+---+---+---+---+
+---------+---+---+---+---+---+---+
| Index | 0 | 1 | 2 | 3 | 4 | 5 |
+---------+---+---+---+---+---+---+
| Pattern | a | b | c | a | b | y |
+---------+---+---+---+---+---+---+
| S | 0 | 0 | 0 | 1 | 2 | 0 |
+---------+---+---+---+---+---+---+
Tenemos un texto, un patrón y una matriz precalculada S usando nuestra lógica definido antes. Comparamos Texto [0] y Patrón [0] y son iguales. El texto [1] y el patrón [1] son iguales. El texto [2] y el patrón [2] no son iguales. Verificamos el valor en la posición justo antes de la falta de coincidencia. Como S [1] es 0 , no hay sufijo que sea el mismo que el prefijo en nuestra subcadena y nuestra comparación comienza en la posición S [1] , que es 0 . Así que el Patrón [0] no es el mismo que el Texto [2] , así que seguimos adelante. El texto [3] es el mismo que el patrón [0] y hay una coincidencia hasta el texto [8] y el patrón [5] . Retrocedemos un paso en la matriz S y encontramos 2 . Entonces, esto significa que hay un prefijo de longitud 2 que también es el sufijo de esta subcadena ( abcab) que es ab . Eso también significa que hay un ab antes del Texto [8] . Así que podemos ignorar con seguridad el Patrón [0] y el Patrón [1] y comenzar nuestra próxima comparación desde el Patrón [2] y el Texto [8] . Si continuamos, encontraremos el patrón en el texto . Nuestro procedimiento se verá como:
Procedure KMP(Text, Pattern)
GenerateSuffixArray(Pattern)
m := Text.Length
n := Pattern.Length
i := 0
j := 0
while i is less than m
if Pattern[j] is equal to Text[i]
j := j + 1
i := i + 1
if j is equal to n
Return (j-i)
else if i < m and Pattern[j] is not equal t Text[i]
if j is not equal to 0
j = S[j-1]
else
i := i + 1
end if
end if
end while
Return -1
La complejidad temporal de este algoritmo, aparte del cálculo de la matriz de sufijo, es O(m) . Como GenerateSuffixArray toma O(n) , la complejidad del tiempo total del algoritmo KMP es: O(m+n) .
PD: Si desea encontrar varias apariciones de Patrón en el Texto , en lugar de devolver el valor, imprímalo / guárdelo y configure j := S[j-1] . También mantenga una flag para rastrear si ha encontrado alguna ocurrencia o no y manejarla en consecuencia.
Implementación Python del algoritmo KMP.
Pajar : La cadena en la que se debe buscar el patrón dado.
Aguja : El patrón a buscar.
Complejidad en el tiempo : la parte de búsqueda (método strstr) tiene la complejidad O (n) donde n es la longitud del pajar, pero como la aguja también se analiza para construir la tabla de prefijos O (m) se requiere para construir la tabla de prefijos donde m es la longitud de la aguja
Por lo tanto, la complejidad de tiempo global para KMP es O (n + m)
Complejidad de espacio : O (m) debido a la tabla de prefijos en la aguja.
Nota: La siguiente implementación devuelve la posición de inicio de la coincidencia en el pajar (si hay una coincidencia) o devuelve -1, para los casos de borde, como si la aguja / el pajar es una cadena vacía o la aguja no se encuentra en el pajar.
def get_prefix_table(needle):
prefix_set = set()
n = len(needle)
prefix_table = [0]*n
delimeter = 1
while(delimeter<n):
prefix_set.add(needle[:delimeter])
j = 1
while(j<delimeter+1):
if needle[j:delimeter+1] in prefix_set:
prefix_table[delimeter] = delimeter - j + 1
break
j += 1
delimeter += 1
return prefix_table
def strstr(haystack, needle):
# m: denoting the position within S where the prospective match for W begins
# i: denoting the index of the currently considered character in W.
haystack_len = len(haystack)
needle_len = len(needle)
if (needle_len > haystack_len) or (not haystack_len) or (not needle_len):
return -1
prefix_table = get_prefix_table(needle)
m = i = 0
while((i<needle_len) and (m<haystack_len)):
if haystack[m] == needle[i]:
i += 1
m += 1
else:
if i != 0:
i = prefix_table[i-1]
else:
m += 1
if i==needle_len and haystack[m-1] == needle[i-1]:
return m - needle_len
else:
return -1
if __name__ == '__main__':
needle = 'abcaby'
haystack = 'abxabcabcaby'
print strstr(haystack, needle)