Entre los algoritmos de búsqueda de coincidencia de cadenas, los dos más famosos son el algoritmo KMP (Knuth-Morris-Pratt) y el algoritmo BM (Boyer-Moore). Ambos algoritmos tienen tiempos de búsqueda lineales en el peor de los casos. Sin embargo, en la práctica, el algoritmo KMP no es mucho más rápido que la función strstr() de la biblioteca C más simple, mientras que el algoritmo BM suele ser de 3 a 5 veces más rápido que el algoritmo KMP (no practicado personalmente). Sin embargo, el algoritmo BM aún no es el algoritmo más rápido. Aquí hay un algoritmo de búsqueda, el algoritmo Sunday, que es más rápido que el algoritmo BM.
La idea del algoritmo Sunday es muy similar a la idea de personajes malos en el algoritmo BM. La única diferencia es que después de que el algoritmo Sunday no logra coincidir, toma el carácter una posición detrás de la parte actual de la cadena de destino que corresponde a la cadena Patrón para realizar una coincidencia incorrecta de caracteres. Cuando se descubre que la coincidencia falla, se juzga si el carácter en el desplazamiento actual + longitud de la cadena del patrón + 1 (se supone que es la posición K) en la cadena principal existe en la cadena del patrón. Si existe, alinee la posición con el carácter en la cadena del Patrón y luego haga coincidir desde el principio. Si no existe, mueva la cadena del Patrón hacia atrás, alinéela con el carácter en k+1 de la cadena principal y luego; fósforo. Repita la operación anterior hasta que la encuentre o hasta que encuentre la cadena principal. Escribí un pequeño ejemplo para implementar el siguiente algoritmo.
En el código, se implementan dos algoritmos de coincidencia de cadenas, uno es el método del domingo y el otro es el método ordinario de mover un bit a la vez. La comparación de eficiencia de los dos se muestra en la función principal, ambos en el nivel de nanosegundos. . Los pasos detallados del algoritmo se han agregado con los comentarios correspondientes en el código. Con respecto al algoritmo BM, lo compararemos y analizaremos juntos la próxima vez que esté vacío.
Copie el código de código de la siguiente manera:
importar java.util.HashMap;
importar java.util.LinkedList;
importar java.util.List;
importar java.util.Map;
/**
* @autor Scott
* @fecha 28 de diciembre de 2013
* @descripción
*/
clase pública SundySearch {
Texto de cadena = nulo;
Patrón de cadena = nulo;
intPosActual = 0;
/**
* Lista de posiciones de los primeros caracteres de la subcadena coincidente
*/
Lista<Integer> matchedPosList = nueva LinkedList<Integer>();
/**
* Mapa de caracteres coincidentes, registra qué caracteres están en la cadena coincidente y el último desplazamiento de cada carácter.
*/
Mapa<Carácter, Entero> map = new HashMap<Carácter, Entero>();
public SundySearch (texto de cadena, patrón de cadena) {
este.texto = texto;
this.pattern = patrón;
this.initMap();
};
/**
* Al hacer coincidir el domingo, se utiliza para almacenar la última posición de aparición de cada carácter en Patrón, en orden de izquierda a derecha.
*/
mapa init vacío privado() {
para (int i = 0; i < patrón.longitud(); i++) {
this.map.put(pattern.charAt(i), i);
}
}
/**
* Coincidencia recursiva de cadenas ordinarias, si la coincidencia falla, avance una posición
*/
Lista pública<Entero> coincidencia normal() {
//No se pudo coincidir, continúa bajando
si (!matchFromSpecialPos(currentPos)) {
PosActual += 1;
if ((text.length() - currentPos) < patrón.length()) {
devolver MatchPosList;
}
coincidencia normal();
} demás {
// Coincidencia exitosa, registra la ubicación
matchedPosList.add(currentPos);
PosActual += 1;
coincidencia normal();
}
devolver MatchPosList;
}
/**
* Coincidencia del domingo, suponiendo que la posición del carácter K en el Texto es: desplazamiento actual + Longitud de la cadena del patrón + 1
*/
Lista pública<Entero> sundayMatch() {
// Si ninguna coincidencia tiene éxito
si (!matchFromSpecialPos(currentPos)) {
// Si el carácter K en Texto no aparece en la cadena del Patrón, omita toda la longitud de la cadena del Patrón.
if ((PosActual + patrón.longitud() + 1) <texto.longitud()
&& !map.containsKey(text.charAt(currentPos + patrón.longitud() + 1))) {
PosActual += patrón.longitud();
}demás {
// Si el carácter K en Texto aparece en la cadena de Patrón, alinee la posición del carácter K en Texto con la posición del último carácter K en la cadena de Patrón.
if ((PosActual + patrón.longitud() + 1) > texto.longitud()) {
PosActual += 1;
} demás {
currentPos += patrón.longitud() - (Entero) map.get(text.charAt(currentPos + patrón.longitud()));
}
}
// Cuando se completa la coincidencia, devuelve el desplazamiento inicial de todas las coincidencias exitosas.
if ((text.length() - currentPos) < patrón.length()) {
devolver MatchedPosList;
}
domingoMatch();
}demás {
// Si la coincidencia es exitosa, avance un bit y luego vuelva a coincidir
matchedPosList.add(currentPos);
PosActual += 1;
domingoMatch();
}
devolver MatchedPosList;
}
/**
* Compruebe si la subcadena que comienza desde el desplazamiento especificado de Texto coincide con el Patrón
*/
coincidencia booleana públicaFromSpecialPos (int pos) {
if ((texto.longitud()-pos) < patrón.longitud()) {
devolver falso;
}
para (int i = 0; i < patrón.longitud(); i++) {
si (texto.charAt(pos + i) == patrón.charAt(i)) {
if (i == (patrón.longitud()-1)) {
devolver verdadero;
}
continuar;
} demás {
romper;
}
}
devolver falso;
}
público estático vacío principal (String [] argumentos) {
SundySearch sundySearch = new SundySearch("hola ah Adolf adfsadfklf adf234masdfsdfdsfdsfdsffwerwrewrerwerwersdf2666sdflsdfk", "adf");
comienzo largo = System.nanoTime();
System.out.println("NormalMatch:" + sundySearch.normalMatch());
System.out.println("NormalMatch:" + (System.nanoTime() - comenzar));
comenzar = System.nanoTime();
System.out.println("SundayMatch:" + sundySearch.sundayMatch());
System.out.println("SundayMatch:" + (System.nanoTime() - comenzar));
}
}