Función prefijo. Algoritmo de Knuth–Morris–Pratt

Definición de la función prefijo

Se nos da un string $s$ de longitud $n$ . La función prefijo (prefix function) de este string se define como un arreglo $\pi$ de longitud $n$ , donde $\pi[i]$ es la longitud del prefijo propio más largo de la subcadena $s[0 \dots i]$ que también es un sufijo de esa subcadena. Un prefijo propio de un string es un prefijo que no es igual al string mismo. Por definición, $\pi[0] = 0$ .

Matemáticamente, la definición de la función prefijo se puede escribir así:

$\pi[i] = \max_ {k = 0 \dots i} {k : s[0 \dots k-1] = s[i-(k-1) \dots i] }$

Por ejemplo, la función prefijo del string “abcabcd” es $[0, 0, 0, 1, 2, 3, 0]$ , y la función prefijo del string “aabaaab” es $[0, 1, 0, 1, 2, 2, 3]$ .

Algoritmo trivial

Un algoritmo que sigue exactamente la definición de la función prefijo es el siguiente:


vector<int> prefix_function(string s) {
    int n = (int)s.length();
    vector<int> pi(n);
    for (int i = 0; i < n; i++)
        for (int k = 0; k <= i; k++)
            if (s.substr(0, k) == s.substr(i-k+1, k))
                pi[i] = k;
    return pi;
}

Es fácil ver que su complejidad es $O(n^3)$ , así que hay margen de mejora.

Algoritmo eficiente

Este algoritmo fue propuesto por Knuth y Pratt y, de forma independiente, por Morris en 1977. Se usó como la función principal de un algoritmo de búsqueda de subcadenas.

Primera optimización

La primera observación importante es que los valores de la función prefijo solo pueden aumentar a lo sumo en uno.

En efecto, de lo contrario, si $\pi[i + 1] \gt \pi[i] + 1$ , podemos tomar este sufijo que termina en la posición $i + 1$ con longitud $\pi[i + 1]$ y quitarle el último carácter. Terminamos con un sufijo que termina en la posición $i$ con longitud $\pi[i + 1] - 1$ , que es mejor que $\pi[i]$ , es decir, obtenemos una contradicción.

La siguiente ilustración muestra esta contradicción. El sufijo propio más largo en la posición $i$ que también es un prefijo tiene longitud $2$ , y en la posición $i+1$ tiene longitud $4$ . Por lo tanto el string $s_0 ~ s_1 ~ s_2 ~ s_3$ es igual al string $s_{i-2} ~ s_{i-1} ~ s_i ~ s_{i+1}$ , lo que significa que también los strings $s_0 ~ s_1 ~ s_2$ y $s_{i-2} ~ s_{i-1} ~ s_i$ son iguales; por lo tanto $\pi[i]$ tiene que ser $3$ .

$\underbrace{\overbrace{s_0 ~ s_1}^{\pi[i] = 2} ~ s_2 ~ s_3}$

Así, al pasar a la siguiente posición, el valor de la función prefijo puede aumentar en uno, permanecer igual o disminuir en cierta cantidad. Este hecho ya nos permite reducir la complejidad del algoritmo a $O(n^2)$ , porque en un paso la función prefijo puede crecer a lo sumo en uno. En total la función puede crecer a lo sumo $n$ pasos, y por lo tanto también solo puede disminuir un total de $n$ pasos. Esto significa que solo tenemos que realizar $O(n)$ comparaciones de strings, y alcanzamos la complejidad $O(n^2)$ .

Segunda optimización

Vayamos más lejos: queremos deshacernos de las comparaciones de strings. Para lograrlo, tenemos que usar toda la información calculada en los pasos anteriores.

Calculemos entonces el valor de la función prefijo $\pi$ para $i + 1$ . Si $s[i+1] = s[\pi[i]]$ , entonces podemos afirmar con certeza que $\pi[i+1] = \pi[i] + 1$ , ya que ya sabemos que el sufijo en la posición $i$ de longitud $\pi[i]$ es igual al prefijo de longitud $\pi[i]$ . Esto se ilustra de nuevo con un ejemplo.

$\underbrace{\overbrace{s_0 ~ s_1 ~ s_2}^{\pi[i]} ~ \overbrace{s_3}^{s_3 = s_{i+1}}}$

Si no es el caso, $s[i+1] \neq s[\pi[i]]$ , entonces tenemos que probar un string más corto. Para acelerar las cosas, nos gustaría pasar de inmediato a la mayor longitud $j \lt \pi[i]$ tal que la propiedad de prefijo se cumple en la posición $i$ , es decir, $s[0 \dots j-1] = s[i-j+1 \dots i]$ :

$\overbrace{\underbrace{s_0 ~ s_1}$

En efecto, si encontramos tal longitud $j$ , entonces de nuevo solo necesitamos comparar los caracteres $s[i+1]$ y $s[j]$ . Si son iguales, podemos asignar $\pi[i+1] = j + 1$ . En caso contrario, tendremos que encontrar el mayor valor menor que $j$ para el cual se cumple la propiedad de prefijo, y así sucesivamente. Puede ocurrir que esto continúe hasta $j = 0$ . Si entonces $s[i+1] = s[0]$ , asignamos $\pi[i+1] = 1$ , y $\pi[i+1] = 0$ en caso contrario.

Así que ya tenemos un esquema general del algoritmo. La única pregunta que queda es cómo encontrar de forma efectiva las longitudes para $j$ . Recapitulemos: para la longitud actual $j$ en la posición $i$ para la cual se cumple la propiedad de prefijo, es decir, $s[0 \dots j-1] = s[i-j+1 \dots i]$ , queremos encontrar el mayor $k \lt j$ para el cual se cumple la propiedad de prefijo.

$\overbrace{\underbrace{s_0 ~ s_1}$

La ilustración muestra que este tiene que ser el valor de $\pi[j-1]$ , que ya calculamos antes.

Algoritmo final

Por fin podemos construir un algoritmo que no realiza ninguna comparación de strings y solo realiza $O(n)$ acciones.

Este es el procedimiento final:

Calculamos los valores de prefijo $\pi[i]$ en un bucle iterando desde $i = 1$ hasta $i = n-1$ (a $\pi[0]$ simplemente se le asigna $0$ ).
Para calcular el valor actual $\pi[i]$ fijamos la variable $j$ que denota la longitud del mejor sufijo para $i-1$ . Inicialmente $j = \pi[i-1]$ .
Comprobamos si el sufijo de longitud $j+1$ también es un prefijo comparando $s[j]$ y $s[i]$ . Si son iguales, asignamos $\pi[i] = j + 1$ ; en caso contrario reducimos $j$ a $\pi[j-1]$ y repetimos este paso.
Si llegamos a la longitud $j = 0$ y todavía no hay coincidencia, entonces asignamos $\pi[i] = 0$ y pasamos al siguiente índice $i + 1$ .

Implementación

La implementación termina siendo sorprendentemente corta y expresiva.


vector<int> prefix_function(string s) {
    int n = (int)s.length();
    vector<int> pi(n);
    for (int i = 1; i < n; i++) {
        int j = pi[i-1];
        while (j > 0 && s[i] != s[j])
            j = pi[j-1];
        if (s[i] == s[j])
            j++;
        pi[i] = j;
    }
    return pi;
}

Este es un algoritmo online, es decir, procesa los datos a medida que llegan: por ejemplo, se pueden leer los caracteres del string uno por uno y procesarlos de inmediato, hallando el valor de la función prefijo para cada siguiente carácter. El algoritmo aún requiere almacenar el string mismo y los valores de la función prefijo calculados previamente, pero si conocemos de antemano el valor máximo $M$ que puede tomar la función prefijo sobre el string, podemos almacenar solo los primeros $M+1$ caracteres del string y la misma cantidad de valores de la función prefijo.

Aplicaciones

Búsqueda de una subcadena en un string. El algoritmo de Knuth-Morris-Pratt

Esta tarea es la aplicación clásica de la función prefijo.

Dados un texto $t$ y un string $s$ , queremos encontrar y mostrar las posiciones de todas las ocurrencias del string $s$ en el texto $t$ .

Por comodidad denotamos con $n$ la longitud del string $s$ y con $m$ la longitud del texto $t$ .

Generamos el string $s + # + t$ , donde $#$ es un separador que no aparece ni en $s$ ni en $t$ . Calculemos la función prefijo de este string. Ahora pensemos en el significado de los valores de la función prefijo, excepto las primeras $n + 1$ entradas (que pertenecen al string $s$ y al separador). Por definición, el valor $\pi[i]$ muestra la mayor longitud de una subcadena que termina en la posición $i$ y que coincide con el prefijo. Pero en nuestro caso esto no es más que el bloque más grande que coincide con $s$ y termina en la posición $i$ . Esta longitud no puede ser mayor que $n$ debido al separador. Pero si se alcanza la igualdad $\pi[i] = n$ , entonces significa que el string $s$ aparece por completo en esta posición, es decir, termina en la posición $i$ . Solo no hay que olvidar que las posiciones están indexadas en el string $s + # + t$ .

Así, si en alguna posición $i$ tenemos $\pi[i] = n$ , entonces en la posición $i - (n + 1) - n + 1 = i - 2n$ del string $t$ aparece el string $s$ .

Como ya se mencionó en la descripción del cálculo de la función prefijo, si sabemos que los valores de prefijo nunca superan cierto valor, entonces no necesitamos almacenar el string entero ni la función entera, sino solo su comienzo. En nuestro caso esto significa que solo necesitamos almacenar el string $s + #$ y los valores de la función prefijo para él. Podemos leer de a un carácter del string $t$ y calcular el valor actual de la función prefijo.

Así, el algoritmo de Knuth-Morris-Pratt resuelve el problema en tiempo $O(n + m)$ y memoria $O(n)$ .

Contar el número de ocurrencias de cada prefijo

Aquí discutimos dos problemas a la vez. Dado un string $s$ de longitud $n$ . En la primera variante del problema queremos contar el número de apariciones de cada prefijo $s[0 \dots i]$ en el mismo string. En la segunda variante se da otro string $t$ y queremos contar el número de apariciones de cada prefijo $s[0 \dots i]$ en $t$ .

Primero resolvemos el primer problema. Consideremos el valor de la función prefijo $\pi[i]$ en una posición $i$ . Por definición, significa que el prefijo de longitud $\pi[i]$ del string $s$ ocurre y termina en la posición $i$ , y no hay un prefijo más largo que cumpla esta definición. Al mismo tiempo, prefijos más cortos pueden terminar en esta posición. No es difícil ver que tenemos la misma pregunta que ya respondimos cuando calculamos la función prefijo misma: Dado un prefijo de longitud $j$ que es un sufijo que termina en la posición $i$ , ¿cuál es el siguiente prefijo más pequeño $\lt j$ que también es un sufijo que termina en la posición $i$ ? Así, en la posición $i$ termina el prefijo de longitud $\pi[i]$ , el prefijo de longitud $\pi[\pi[i] - 1]$ , el prefijo $\pi[\pi[\pi[i] - 1] - 1]$ , y así sucesivamente, hasta que el índice se vuelve cero. Así podemos calcular la respuesta de la siguiente forma.


vector<int> ans(n + 1);
for (int i = 0; i < n; i++)
    ans[pi[i]]++;
for (int i = n-1; i > 0; i--)
    ans[pi[i-1]] += ans[i];
for (int i = 0; i <= n; i++)
    ans[i]++;

Aquí, para cada valor de la función prefijo primero contamos cuántas veces ocurre en el arreglo $\pi$ , y luego calculamos las respuestas finales: si sabemos que el prefijo de longitud $i$ aparece exactamente $\text{ans}[i]$ veces, entonces este número hay que sumarlo al número de ocurrencias de su sufijo más largo que también es un prefijo. Al final hay que sumar $1$ a cada resultado, ya que también hay que contar los prefijos originales.

Ahora consideremos el segundo problema. Aplicamos el truco de Knuth-Morris-Pratt: creamos el string $s + # + t$ y calculamos su función prefijo. Las únicas diferencias con la primera tarea son que solo nos interesan los valores de prefijo que se relacionan con el string $t$ , es decir, $\pi[i]$ para $i \ge n + 1$ . Con esos valores podemos realizar exactamente los mismos cálculos que en la primera tarea.

El número de subcadenas distintas en un string

Dado un string $s$ de longitud $n$ . Queremos calcular el número de subcadenas distintas que aparecen en él.

Resolveremos este problema de forma iterativa. A saber, aprenderemos, conociendo el número actual de subcadenas distintas, cómo recalcular este conteo al agregar un carácter al final.

Sea $k$ el número actual de subcadenas distintas en $s$ , y agregamos el carácter $c$ al final de $s$ . Obviamente aparecerán algunas subcadenas nuevas que terminan en $c$ . Queremos contar estas subcadenas nuevas que no aparecieron antes.

Tomamos el string $t = s + c$ y lo invertimos. Ahora la tarea se transforma en calcular cuántos prefijos hay que no aparecen en ningún otro lugar. Si calculamos el valor máximo de la función prefijo $\pi_{\text{max}}$ del string invertido $t$ , entonces el prefijo más largo que aparece en $s$ tiene longitud $\pi_{\text{max}}$ . Claramente, también aparecen todos los prefijos de menor longitud.

Por lo tanto, el número de subcadenas nuevas que aparecen cuando agregamos un nuevo carácter $c$ es $|s| + 1 - \pi_{\text{max}}$ .

Así, por cada carácter agregado podemos calcular el número de subcadenas nuevas en tiempo $O(n)$ , lo que da una complejidad temporal de $O(n^2)$ en total.

Vale la pena notar que también podemos calcular el número de subcadenas distintas agregando los caracteres al principio, o eliminando caracteres del principio o del final.

Comprimir un string

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

Está claro que solo necesitamos encontrar la longitud de $t$ . Conociendo la longitud, la respuesta al problema será el prefijo de $s$ con esa longitud.

Calculemos la función prefijo de $s$ . Usando su último valor definimos el valor $k = n - \pi[n - 1]$ . Mostraremos que si $k$ divide a $n$ , entonces $k$ será la respuesta; en caso contrario no hay una compresión efectiva y la respuesta es $n$ .

Sea $n$ divisible por $k$ . Entonces el string se puede particionar en bloques de longitud $k$ . Por definición de la función prefijo, el prefijo de longitud $n - k$ será igual a su sufijo. Pero esto significa que el último bloque es igual al bloque anterior. Y el bloque anterior tiene que ser igual al bloque que lo precede. Y así sucesivamente. Como resultado, resulta que todos los bloques son iguales, por lo tanto podemos comprimir el string $s$ a longitud $k$ .

Por supuesto, todavía hay que mostrar que esto es realmente el óptimo. En efecto, si hubiera una compresión menor que $k$ , entonces la función prefijo al final sería mayor que $n - k$ . Por lo tanto $k$ es realmente la respuesta.

Ahora supongamos que $n$ no es divisible por $k$ . Mostramos que esto implica que la longitud de la respuesta es $n$ . Lo demostramos por contradicción. Suponiendo que existe una respuesta, y que la compresión tiene longitud $p$ ( $p$ divide a $n$ ). Entonces el último valor de la función prefijo tiene que ser mayor que $n - p$ , es decir, el sufijo cubrirá parcialmente el primer bloque. Ahora consideremos el segundo bloque del string. Como el prefijo es igual al sufijo, y tanto el prefijo como el sufijo cubren este bloque y su desplazamiento relativo $k$ no divide la longitud del bloque $p$ (de lo contrario $k$ dividiría a $n$ ), entonces todos los caracteres del bloque tienen que ser idénticos. Pero entonces el string consiste en un solo carácter repetido una y otra vez, por lo tanto podemos comprimirlo a un string de tamaño $1$ , lo que da $k = 1$ , y $k$ divide a $n$ . Contradicción.

$\overbrace{s_0 ~ s_1 ~ s_2 ~ s_3}^p ~ \overbrace{s_4 ~ s_5 ~ s_6 ~ s_7}^p$

$s_0 ~ s_1 ~ s_2 ~ \underbrace{\overbrace{s_3 ~ s_4 ~ s_5 ~ s_6}^p ~ s_7}_{\pi[7] = 5}$

$s_4 = s_3, ~ s_5 = s_4, ~ s_6 = s_5, ~ s_7 = s_6 ~ \Rightarrow ~ s_0 = s_1 = s_2 = s_3$

Construir un autómata según la función prefijo

Volvamos a la concatenación de los dos strings a través de un separador, es decir, para los strings $s$ y $t$ calculamos la función prefijo del string $s + # + t$ . Obviamente, como $#$ es un separador, el valor de la función prefijo nunca superará $|s|$ . Se sigue que basta con almacenar solo el string $s + #$ y los valores de la función prefijo para él, y podemos calcular la función prefijo para todo carácter posterior sobre la marcha:

$\underbrace{s_0 ~ s_1 ~ \dots ~ s_{n-1} ~ #}$

En efecto, en tal situación, conocer el siguiente carácter $c \in t$ y el valor de la función prefijo de la posición anterior es información suficiente para calcular el siguiente valor de la función prefijo, sin usar ningún carácter anterior del string $t$ ni el valor de la función prefijo en ellos.

En otras palabras, podemos construir un autómata (una máquina de estados finitos): el estado en él es el valor actual de la función prefijo, y la transición de un estado a otro se realizará mediante el siguiente carácter.

Así, incluso sin tener el string $t$ , podemos construir una tabla de transiciones $(\text{old}$ usando el mismo algoritmo que para calcular la tabla de transiciones:


void compute_automaton(string s, vector<vector<int>>& aut) {
    s += '#';
    int n = s.size();
    vector<int> pi = prefix_function(s);
    aut.assign(n, vector<int>(26));
    for (int i = 0; i < n; i++) {
        for (int c = 0; c < 26; c++) {
            int j = i;
            while (j > 0 && 'a' + c != s[j])
                j = pi[j-1];
            if ('a' + c == s[j])
                j++;
            aut[i][c] = j;
        }
    }
}

Sin embargo, en esta forma el algoritmo corre en tiempo $O(n^2 26)$ para las letras minúsculas del alfabeto. Nótese que podemos aplicar programación dinámica y usar las partes de la tabla ya calculadas. Cada vez que vamos del valor $j$ al valor $\pi[j-1]$ , en realidad queremos decir que la transición $(j, c)$ lleva al mismo estado que la transición $(\pi[j-1], c)$ , y esta respuesta ya está calculada con precisión.


void compute_automaton(string s, vector<vector<int>>& aut) {
    s += '#';
    int n = s.size();
    vector<int> pi = prefix_function(s);
    aut.assign(n, vector<int>(26));
    for (int i = 0; i < n; i++) {
        for (int c = 0; c < 26; c++) {
            if (i > 0 && 'a' + c != s[i])
                aut[i][c] = aut[pi[i-1]][c];
            else
                aut[i][c] = i + ('a' + c == s[i]);
        }
    }
}

Como resultado construimos el autómata en tiempo $O(26 n)$ .

¿Cuándo es útil un autómata así? Para empezar, recordemos que usamos la función prefijo del string $s + # + t$ y sus valores principalmente para un solo propósito: encontrar todas las ocurrencias del string $s$ en el string $t$ .

Por lo tanto, el beneficio más obvio de este autómata es la aceleración del cálculo de la función prefijo para el string $s + # + t$ . Al construir el autómata para $s + #$ , ya no necesitamos almacenar el string $s$ ni los valores de la función prefijo en él. Todas las transiciones ya están calculadas en la tabla.

Pero hay una segunda aplicación, menos obvia. Podemos usar el autómata cuando el string $t$ es un string gigantesco construido usando algunas reglas. Esto puede ser, por ejemplo, los strings de Gray, o un string formado por una combinación recursiva de varios strings cortos de la entrada.

Para completar resolveremos un problema de este tipo: dados un número $k \le 10^5$ y un string $s$ de longitud $\le 10^5$ . Tenemos que calcular el número de ocurrencias de $s$ en el $k$ -ésimo string de Gray. Recordemos que los strings de Gray se definen de la siguiente forma:

$\begin{aligned} g_{1} & = “a” \\ g_{2} & = “aba” \\ g_{3} & = “abacaba” \\ g_{4} & = “abacabadabacaba” \end{aligned}$

En tales casos, incluso construir el string $t$ será imposible, por su longitud astronómica. El $k$ -ésimo string de Gray tiene $2^k-1$ caracteres de longitud. Sin embargo, podemos calcular el valor de la función prefijo al final del string de forma efectiva, conociendo solo el valor de la función prefijo al inicio.

Además del autómata mismo, también calculamos valores $G[i][j]$ : el valor del autómata después de procesar el string $g_i$ partiendo del estado $j$ . Y adicionalmente calculamos valores $K[i][j]$ : el número de ocurrencias de $s$ en $g_i$ durante el procesamiento de $g_i$ partiendo del estado $j$ . En realidad $K[i][j]$ es el número de veces que la función prefijo tomó el valor $|s|$ al realizar las operaciones. La respuesta al problema será entonces $K[k][0]$ .

¿Cómo podemos calcular estos valores? Primero, los valores básicos son $G[0][j] = j$ y $K[0][j] = 0$ . Y todos los valores posteriores se pueden calcular a partir de los valores anteriores y usando el autómata. Para calcular el valor para algún $i$ recordamos que el string $g_i$ consiste en $g_{i-1}$ , el $i$ -ésimo carácter del alfabeto, y $g_{i-1}$ . Así el autómata irá al estado:

$\text{mid} = \text{aut}[G[i-1][j]][i]$

$G[i][j] = G[i-1][\text{mid}]$

Los valores de $K[i][j]$ también se pueden contar fácilmente.

$K[i][j] = K[i-1][j] + (\text{mid} == |s|) + K[i-1][\text{mid}]$

Así podemos resolver el problema para strings de Gray, y de forma similar también una enorme cantidad de otros problemas parecidos. Por ejemplo, el mismo método también resuelve el siguiente problema: se nos da un string $s$ y algunos patrones $t_i$ , cada uno de los cuales se especifica así: es un string de caracteres ordinarios, y puede haber algunas inserciones recursivas de los strings anteriores de la forma $t_k^{\text{cnt}}$ , lo que significa que en ese lugar hay que insertar el string $t_k$ $\text{cnt}$ veces. Un ejemplo de tales patrones:

$\begin{aligned} t_{1} & = “abdeca” \\ t_{2} & = “abc” + t_{1}^{30} + “abd” \\ t_{3} & = t_{2}^{50} + t_{1}^{100} \\ t_{4} & = t_{2}^{10} + t_{3}^{100} \end{aligned}$

Las sustituciones recursivas inflan el string, de modo que sus longitudes pueden alcanzar el orden de $100^{100}$ .

Tenemos que encontrar el número de veces que el string $s$ aparece en cada uno de los strings.

El problema se puede resolver de la misma forma construyendo el autómata de la función prefijo, y luego calculamos las transiciones para cada patrón usando los resultados anteriores.