El algoritmo Z encuentra todas las ocurrencias de un patrón en un texto en tiempo lineal. Siendo la longitud del texto n y la longitud del patrón m, la complejidad es O(n + m), lineal. Se puede observar que la complejidad es la misma que el algoritmo KMP, sin embargo el algoritmo Z es más sencillo de entender. Todo parte de la construcción del array Z.
Qué es el Array Z
Para un String str[0..n-1], su array Z tiene la misma longitud. Un elemento Z[i] del array Z almacena la longitud de la sub-cadena más larga empezando por str[i]. La primera entrada del array Z tiene menos peso ya que que el String completo es un prefijo de si mismo. Ejemplo:
Índice 0 1 2 3 4 5 6 7 8 9 10 11
Texto a a b c a a b x a a a z
Valores Z X 1 0 0 3 1 0 0 2 2 1 0str = "aabaacd"
Z[] = {x, 1, 0, 2, 1, 0, 0}Algoritmo Z y complejidad lineal
La idea es concatenar patrón y texto y generar una cadena “P$T”. Donde P es el patrón a encontrar y $ es un carácter especial que no debe estar presente en el patrón ni en el texto, y T es el texto. En el array Z, si el valor Z en cualquier punto es igual a la longitud del patrón, entonces el patrón está presente en ese punto. Ejemplo:
Patron P = "aab", Texto T = "baabaa"
Cadena concatenada = "aab$baabaa"
Array Z para la cadena concatenada = {x, 1, 0, 0, 0,
3, 1, 0, 2, 1}.
Como la longitud del patrón es 3, el valor 3 del array Z indica la presencia del patrón
Como construir el array Z
Una solución sencilla para construirlo es con dos bucles anidados. El bucle exterior recorre todos los índices y el bucle interno encuentra la longitud del prefijo más largo que coincide con la sub-cadena empezando por el índice actual. La complejidad de esta solución es de O(n2).
Implementación Java
class DeteccionPatronesZ {
public static void busqueda(String texto, String patron)
{
// Crear la cadena concatenada "P$T"
String concatenado = patron + "$" + texto;
int longitud = concatenado.length();
int Z[] = new int[longitud];
// Construye el array Z
obtenerArrayZ(concatenado, Z);
// iteramos sobre el array Z
for(int i = 0; i < longitud; ++i){
// si Z[i] es igual a la longitud del patron, lo tenemos identificado
if(Z[i] == patron.length()){
System.out.println("Patron encontrado en el indice "
+ (i - patron.length() - 1));
}
}
}
private static void obtenerArrayZ(String cadena, int[] Z) {
int n = cadena.length();
int L = 0, R = 0;
for(int i = 1; i < n; ++i) {
if(i > R){
L = R = i;
// R-L = 0 al inicio, empezara comprobando desde el indice 0.
// Por ejemplo, para "ababab" e i=1, el valor de R
// permanece 0 y Z[i] se vuelve 0. Para la cadena "aaaaaa"
// e i=1, Z[i]y R valen 5.
while(R < n && cadena.charAt(R - L) == cadena.charAt(R))
R++;
Z[i] = R - L;
R--;
}
else{
int k = i - L;
// Por ejemplo, cadena= "ababab", i = 3, R = 5
// y L = 2
if(Z[k] < R - i + 1)
Z[i]=Z[k];
else{
L = i;
while(R < n && cadena.charAt(R - L)== cadena.charAt(R))
R++;
Z[i]= R-L;
R--;
}
}
}
}
public static void main(String[] args)
{
String texto = "pruebas y mas pruebas";
String patron = "prueba";
search(texto, patron);
}
}
Más algoritmos de ordenación y búsqueda
| Asunto | Descripción |
| Ordenación Burbuja | Ordenación algoritmo BubbleSort. |
| Ordenación Inserción | Algoritmo de ordenación por inserción |
| Ordenación Selección | Algoritmo de ordenación por selección |
| Ordenación Quicksort | Algoritmo de ordenación eficiente Quicksort |
| Búsqueda Binaria | Algoritmo de búsqueda binaria |
| Patrones: Algoritmo Z | Detección de patrones con algoritmo Z |
| Patrones: Algoritmo Naive | Detectar patrones con algoritmo ingenuo o naive |
| Algoritmo de Dijkstra | Como encontrar el camino más corto entre dos nodos en un grafo ponderado |
| Algoritmo de Kruskal | Se utiliza para encontrar el árbol de expansión mínimo en un grafo ponderado |
Recursos básicos Java
| Asunto | Descripción |
| Tutorial básico y sintaxis | Tutorial básico Java y sintaxis. Aprende los fundamentos del lenguaje. |
| Hilos (Threads) | Aprende a manejar hilos y las cuestiones básicas de la concurrencia |
| Funciones Lambda | Aquí te enseñamos las nociones más importantes para arrancas con funciones lambda |
| Palíndromos | Programa de ejemplo para el uso de palíndromos en Java. |
| Máquina Virtual de Java | Te explicamos el funcionamiento de la máquina virtual de java (Java Virtual Machine – JVM) |
| JDK, JRE y JVM | Diferencias entre el JDK, JRE y JVM. |
| Mejores libros Java en Español | Hazte con los mejores libros Java para aprender paso a paso y profundizar en las mejores prácticas |
| TensorFlow | Manejo del API de TensorFlow para la construcción de grafos de operaciones y su ejecución |
| Tutorial Log4j | Tutorial para el manejo de Log4j, herramienta ágil y flexible para la gestión de Logs en Java |
| Java Security | Entiende y aplica las posibilidades que da Java para mantener la seguridad |
| Tutorial JConsole | Aprende los conceptos básicos de monitorización de procesos Java con JConsole |
| JavaFX | Tutorial de JavaFX, librería gráfica moderna para construcción de GUIs en móvil, escritorio y web. |
| Estructuras de datos en Java | Explicación y ejemplos de las estructuras de datos más importantes: listas, pila, cola, arbol. |
| Javaapi | Conjunto de clases, interfaces, métodos y paquetes que forman parte de la plataforma Java estándar |
| Algoritmo Huffman | Método eficiente para codificar datos, asignando códigos más cortos a los caracteres más frecuentes |