Función Z y su cálculo

Supongamos que se nos da un string $s$ de longitud $n$ . La función Z (Z-function) de este string es un arreglo de longitud $n$ donde el $i$ -ésimo elemento es igual a la mayor cantidad de caracteres a partir de la posición $i$ que coinciden con los primeros caracteres de $s$ .

En otras palabras, $z[i]$ es la longitud del string más largo que es, al mismo tiempo, un prefijo de $s$ y un prefijo del sufijo de $s$ que empieza en $i$ .

Nota. En este artículo, para evitar ambigüedad, asumimos índices basados en $0$ ; es decir: el primer carácter de $s$ tiene índice $0$ y el último tiene índice $n-1$ .

El primer elemento de la función Z, $z[0]$ , en general no está bien definido. En este artículo asumiremos que es cero (aunque no cambia nada en la implementación del algoritmo).

Este artículo presenta un algoritmo para calcular la función Z en tiempo $O(n)$ , además de varias de sus aplicaciones.

Ejemplos

Por ejemplo, estos son los valores de la función Z calculados para distintos strings:

“aaaaa” - $[0, 4, 3, 2, 1]$
“aaabaab” - $[0, 2, 1, 0, 2, 1, 0]$
“abacaba” - $[0, 0, 1, 0, 3, 0, 1]$

Algoritmo trivial

La definición formal se puede representar con la siguiente implementación elemental $O(n^2)$ .


vector<int> z_function_trivial(string s) {
	int n = s.size();
	vector<int> z(n);
	for (int i = 1; i < n; i++) {
		while (i + z[i] < n && s[z[i]] == s[i + z[i]]) {
			z[i]++;
		}
	}
	return z;
}

Simplemente iteramos por cada posición $i$ y actualizamos $z[i]$ para cada una, partiendo de $z[i] = 0$ e incrementándolo mientras no encontremos una discrepancia (y mientras no lleguemos al final del string).

Por supuesto, esta no es una implementación eficiente. Ahora mostraremos la construcción de una implementación eficiente.

Algoritmo eficiente para calcular la función Z

Para obtener un algoritmo eficiente calcularemos los valores de $z[i]$ uno tras otro desde $i = 1$ hasta $n - 1$ , pero al mismo tiempo, al calcular un valor nuevo, intentaremos aprovechar al máximo los valores ya calculados.

Por brevedad, llamemos coincidencias de segmento a aquellas subcadenas que coinciden con un prefijo de $s$ . Por ejemplo, el valor de la función Z buscada $z[i]$ es la longitud de la coincidencia de segmento que empieza en la posición $i$ (y que termina en la posición $i + z[i] - 1$ ).

Para hacer esto, mantendremos los índices $[l, r)$ de la coincidencia de segmento más a la derecha. Es decir, entre todos los segmentos detectados nos quedaremos con el que termina más a la derecha. En cierto modo, el índice $r$ se puede ver como la “frontera” hasta la cual el algoritmo ya recorrió el string $s$ ; todo lo que está más allá de ese punto todavía no se conoce.

Entonces, si el índice actual (para el cual hay que calcular el siguiente valor de la función Z) es $i$ , tenemos una de dos opciones:

$i \geq r$ — la posición actual está fuera de lo que ya procesamos.

Calcularemos entonces $z[i]$ con el algoritmo trivial (es decir, comparando los valores uno por uno). Nótese que al final, si $z[i] > 0$ , habrá que actualizar los índices del segmento más a la derecha, porque está garantizado que el nuevo $r = i + z[i]$ es mejor que el $r$ anterior.
$i < r$ — la posición actual está dentro de la coincidencia de segmento actual $[l, r)$ .

Entonces podemos usar los valores Z ya calculados para “inicializar” el valor de $z[i]$ a algo (seguro que es mejor que “empezar desde cero”), tal vez incluso un número grande.

Para esto, observamos que las subcadenas $s[l \dots r)$ y $s[0 \dots r-l)$ coinciden. Esto significa que como aproximación inicial de $z[i]$ podemos tomar el valor ya calculado para el segmento correspondiente $s[0 \dots r-l)$ , y ese es $z[i-l]$ .

Sin embargo, el valor $z[i-l]$ podría ser demasiado grande: al aplicarlo a la posición $i$ podría superar el índice $r$ . Esto no está permitido porque no sabemos nada de los caracteres a la derecha de $r$ : pueden diferir de los requeridos.

Aquí hay un ejemplo de un escenario similar:

$s = “aaaabaa”$

Cuando llegamos a la última posición ( $i = 6$ ), el segmento de coincidencia actual será $[5, 7)$ . La posición $6$ coincidirá entonces con la posición $6 - 5 = 1$ , para la cual el valor de la función Z es $z[1] = 3$ . Obviamente, no podemos inicializar $z[6]$ en $3$ , sería completamente incorrecto. El valor máximo al que podríamos inicializarlo es $1$ — porque es el mayor valor que no nos lleva más allá del índice $r$ del segmento de coincidencia $[l, r)$ .

Así, como aproximación inicial de $z[i]$ podemos tomar de forma segura:

$z_0[i] = \min(r - i,; z[i-l])$

Después de haber inicializado $z[i]$ en $z_0[i]$ , intentamos incrementar $z[i]$ ejecutando el algoritmo trivial — porque en general, después de la frontera $r$ , no podemos saber si el segmento seguirá coincidiendo o no.

Así, el algoritmo completo se parte en dos casos, que solo difieren en el valor inicial de $z[i]$ : en el primer caso se asume que es cero, en el segundo se determina a partir de los valores ya calculados (usando la fórmula de arriba). Después de eso, ambas ramas de este algoritmo se pueden reducir a la implementación del algoritmo trivial, que empieza inmediatamente después de especificar el valor inicial.

El algoritmo resulta ser muy simple. A pesar de que en cada iteración se ejecuta el algoritmo trivial, hemos avanzado de forma significativa, y tenemos un algoritmo que corre en tiempo lineal. Más adelante demostraremos que el tiempo de ejecución es lineal.

Implementación

La implementación resulta bastante concisa:


vector<int> z_function(string s) {
    int n = s.size();
    vector<int> z(n);
    int l = 0, r = 0;
    for(int i = 1; i < n; i++) {
        if(i < r) {
            z[i] = min(r - i, z[i - l]);
        }
        while(i + z[i] < n && s[z[i]] == s[i + z[i]]) {
            z[i]++;
        }
        if(i + z[i] > r) {
            l = i;
            r = i + z[i];
        }
    }
    return z;
}

Comentarios sobre esta implementación

Toda la solución se da como una función que devuelve un arreglo de longitud $n$ — la función Z de $s$ .

El arreglo $z$ se inicializa con ceros. El segmento de coincidencia más a la derecha actual se asume $[0; 0)$ (es decir, un segmento deliberadamente pequeño que no contiene ningún $i$ ).

Dentro del bucle para $i = 1 \dots n - 1$ primero determinamos el valor inicial $z[i]$ — o bien permanecerá en cero, o se calculará con la fórmula de arriba.

A continuación, el algoritmo trivial intenta aumentar el valor de $z[i]$ tanto como sea posible.

Al final, si hace falta (es decir, si $i + z[i] > r$ ), actualizamos el segmento de coincidencia más a la derecha $[l, r)$ .

Comportamiento asintótico del algoritmo

Demostraremos que el algoritmo de arriba tiene un tiempo de ejecución lineal en la longitud del string — es decir, es $O(n)$ .

La demostración es muy simple.

Nos interesa el bucle while anidado, ya que todo lo demás es solo un conjunto de operaciones constantes que suman $O(n)$ .

Mostraremos que cada iteración del bucle while aumentará el borde derecho $r$ del segmento de coincidencia.

Para eso, consideraremos ambas ramas del algoritmo:

$i \geq r$

En este caso, o bien el bucle while no hará ninguna iteración (si $s[0] \ne s[i]$ ), o tomará algunas iteraciones, empezando en la posición $i$ , cada vez moviéndose un carácter a la derecha. Después de eso, el borde derecho $r$ se actualizará necesariamente.

Así, hemos encontrado que, cuando $i \geq r$ , cada iteración del bucle while aumenta el valor del nuevo índice $r$ .
$i < r$

En este caso, inicializamos $z[i]$ en cierto valor $z_0$ dado por la fórmula de arriba. Comparemos este valor inicial $z_0$ con el valor $r - i$ . Tendremos tres casos:
- $z_0 < r - i$
  
  Demostramos que en este caso no tendrá lugar ninguna iteración del bucle while.
  
  Es fácil de demostrar, por ejemplo, por contradicción: si el bucle while hiciera al menos una iteración, significaría que la aproximación inicial $z[i] = z_0$ era inexacta (menor que la longitud real de la coincidencia). Pero como $s[l \dots r)$ y $s[0 \dots r-l)$ son iguales, esto implicaría que $z[i-l]$ tiene el valor incorrecto (menor de lo que debería).
  
  Así, como $z[i-l]$ es correcto y es menor que $r - i$ , se sigue que este valor coincide con el valor requerido $z[i]$ .
- $z_0 = r - i$
  
  En este caso, el bucle while puede hacer algunas iteraciones, pero cada una de ellas llevará a un aumento del valor del índice $r$ porque empezaremos a comparar desde $s[r]$ , lo que subirá más allá del intervalo $[l, r)$ .
- $z_0 > r - i$
  
  Esta opción es imposible, por definición de $z_0$ .

Así, hemos demostrado que cada iteración del bucle interno hace que el puntero $r$ avance hacia la derecha. Como $r$ no puede ser mayor que $n-1$ , esto significa que el bucle interno no hará más de $n-1$ iteraciones.

Como el resto del algoritmo obviamente trabaja en $O(n)$ , hemos demostrado que el algoritmo completo para calcular funciones Z corre en tiempo lineal.

Aplicaciones

Ahora consideraremos algunos usos de las funciones Z para tareas específicas.

Estas aplicaciones serán en gran medida similares a las aplicaciones de la función prefijo.

Búsqueda de la subcadena

Para evitar confusión, llamamos $t$ al string de texto, y $p$ al patrón. El problema es: encontrar todas las ocurrencias del patrón $p$ dentro del texto $t$ .

Para resolver este problema, creamos un nuevo string $s = p + \diamond + t$ , es decir, concatenamos $p$ y $t$ pero además colocamos un carácter separador $\diamond$ en el medio (elegiremos $\diamond$ de modo que con certeza no esté presente en ninguna parte de los strings $p$ o $t$ ).

Calculamos la función Z de $s$ . Luego, para cualquier $i$ en el intervalo $[0; ; \operatorname{length}(t) - 1]$ , consideraremos el valor correspondiente $k = z[i + \operatorname{length}(p) + 1]$ . Si $k$ es igual a $\operatorname{length}(p)$ entonces sabemos que hay una ocurrencia de $p$ en la $i$ -ésima posición de $t$ ; en caso contrario no hay ocurrencia de $p$ en la $i$ -ésima posición de $t$ .

El tiempo de ejecución (y el consumo de memoria) es $O(\operatorname{length}(t) + \operatorname{length}(p))$ .

Número de subcadenas distintas en un string

Dado un string $s$ de longitud $n$ , contar el número de subcadenas distintas de $s$ .

Resolveremos este problema de forma iterativa. Es decir: conociendo el número actual de subcadenas distintas, recalcular esta cantidad después de agregar al final de $s$ un carácter.

Sea $k$ el número actual de subcadenas distintas de $s$ . Agregamos un nuevo carácter $c$ a $s$ . Obviamente, puede haber algunas subcadenas nuevas que terminan en este nuevo carácter $c$ (a saber, todos aquellos strings que terminan con este símbolo y que todavía no habíamos encontrado).

Tomamos un string $t = s + c$ y lo invertimos (escribimos sus caracteres en orden inverso). Nuestra tarea ahora es contar cuántos prefijos de $t$ no se encuentran en ninguna otra parte de $t$ . Calculemos la función Z de $t$ y encontremos su valor máximo $z_{max}$ . Obviamente, el prefijo de $t$ de longitud $z_{max}$ también ocurre en algún lugar del medio de $t$ . Claramente, los prefijos más cortos también ocurren.

Así, hemos encontrado que el número de subcadenas nuevas que aparecen cuando se agrega el símbolo $c$ a $s$ es igual a $\operatorname{length}(t) - z_{max}$ .

En consecuencia, el tiempo de ejecución de esta solución es $O(n^2)$ para un string de longitud $n$ .

Vale la pena notar que exactamente de la misma forma podemos recalcular, todavía en tiempo $O(n)$ , el número de subcadenas distintas al agregar un carácter al principio del string, y también al eliminarlo (del final o del principio).

Compresión de un string

Dado un string $s$ de longitud $n$ . Encontrar su representación “comprimida” más corta, es decir: encontrar un string $t$ de menor longitud tal que $s$ se pueda representar como concatenación de una o más copias de $t$ .

Una solución es: calcular la función Z de $s$ , recorrer todos los $i$ tales que $i$ divide a $n$ . Detenerse en el primer $i$ tal que $i + z[i] = n$ . Entonces, el string $s$ se puede comprimir a la longitud $i$ .

La demostración de este hecho es la misma que la de la solución que usa la función prefijo.