algorithm
Algoritmo de Knuth Morris Pratt (KMP)
Buscar..
Introducción
El KMP es un algoritmo de coincidencia de patrones que busca las apariciones de una "palabra" W dentro de una "cadena de texto" principal S empleando la observación de que cuando se produce una discrepancia, tenemos la información suficiente para determinar dónde podría comenzar la siguiente coincidencia. aproveche esta información para evitar que coincidan los caracteres que sabemos que de todos modos coincidirán. La complejidad del peor de los casos para buscar un patrón se reduce a O (n) .
Ejemplo de KMP
Algoritmo
Este algoritmo es un proceso de dos pasos. Primero creamos una matriz auxiliar lps [] y luego usamos esta matriz para buscar el patrón.
Preprocesamiento
- Preprocesamos el patrón y creamos una matriz auxiliar lps [] que se usa para omitir caracteres al hacer coincidir.
- Aquí lps [] indica el prefijo apropiado más largo que también es sufijo. Un prefijo apropiado es el prefijo en el que no se incluye la cadena completa. Por ejemplo, los prefijos de la cadena ABC son “” , “A” , “AB” y “ABC” . Los prefijos apropiados son “” , “A” y “AB” . Los sufijos de la cadena son "" , "C" , "BC" y "ABC" .
buscando
Seguimos combinando los caracteres txt [i] y pat [j] y seguimos incrementando i y j mientras pat [j] y txt [i] siguen coincidiendo.
Cuando vemos una discrepancia, sabemos que los caracteres pat [0..j-1] coinciden con txt [i-j + 1… i-1]. También sabemos que lps [j-1] es el recuento de caracteres de pat [0… j-1] que son el prefijo y el sufijo propios. De esto podemos concluir que no necesitamos hacer coincidir estos caracteres lps [j-1] con txt [ij ... i-1] porque sabemos que estos caracteres coincidirá de todos modos.
Implementación en Java
public class KMP {
public static void main(String[] args) {
// TODO Auto-generated method stub
String str = "abcabdabc";
String pattern = "abc";
KMP obj = new KMP();
System.out.println(obj.patternExistKMP(str.toCharArray(), pattern.toCharArray()));
}
public int[] computeLPS(char[] str){
int lps[] = new int[str.length];
lps[0] = 0;
int j = 0;
for(int i =1;i<str.length;i++){
if(str[j] == str[i]){
lps[i] = j+1;
j++;
i++;
}else{
if(j!=0){
j = lps[j-1];
}else{
lps[i] = j+1;
i++;
}
}
}
return lps;
}
public boolean patternExistKMP(char[] text,char[] pat){
int[] lps = computeLPS(pat);
int i=0,j=0;
while(i<text.length && j<pat.length){
if(text[i] == pat[j]){
i++;
j++;
}else{
if(j!=0){
j = lps[j-1];
}else{
i++;
}
}
}
if(j==pat.length)
return true;
return false;
}
}