Encontrar repeticiones

Se da un string $s$ de longitud $n$ .

Una repetición es dos ocurrencias de un string seguidas. En otras palabras, una repetición se puede describir por un par de índices $i < j$ tales que la subcadena $s[i \dots j]$ consiste en dos strings idénticos escritos uno después del otro.

El desafío es encontrar todas las repeticiones en un string dado $s$ . O una tarea simplificada: encontrar alguna repetición o encontrar la repetición más larga.

El algoritmo descrito aquí fue publicado en 1982 por Main y Lorentz.

Ejemplo

Consideremos las repeticiones en el siguiente string de ejemplo:

$acababaee$

El string contiene las siguientes tres repeticiones:

$s[2 \dots 5] = abab$
$s[3 \dots 6] = baba$
$s[7 \dots 8] = ee$

Otro ejemplo:

$abaaba$

Aquí hay solo dos repeticiones

$s[0 \dots 5] = abaaba$
$s[2 \dots 3] = aa$

Número de repeticiones

En general puede haber hasta $O(n^2)$ repeticiones en un string de longitud $n$ . Un ejemplo obvio es un string que consiste en $n$ veces la misma letra; en este caso cualquier subcadena de longitud par es una repetición. En general cualquier string periódico con un período corto contendrá muchas repeticiones.

Por otro lado, este hecho no impide computar el número de repeticiones en tiempo $O(n \log n)$ , porque el algoritmo puede dar las repeticiones en forma comprimida, en grupos de varias piezas a la vez.

Existe incluso el concepto que describe grupos de subcadenas periódicas con tuplas de tamaño cuatro. Se ha demostrado que el número de tales grupos es a lo sumo lineal respecto de la longitud del string.

Además, aquí hay algunos resultados más interesantes relacionados con el número de repeticiones:

El número de repeticiones primitivas (aquellas cuyas mitades no son repeticiones) es a lo sumo $O(n \log n)$ .
Si codificamos las repeticiones con tuplas de números (llamadas triples de Crochemore) $(i,~ p,~ r)$ (donde $i$ es la posición del comienzo, $p$ la longitud de la subcadena que se repite, y $r$ el número de repeticiones), entonces todas las repeticiones se pueden describir con $O(n \log n)$ de tales triples.
Los strings de Fibonacci, definidos como

$\begin{aligned} t_{0} & = a, \\ t_{1} & = b, \\ t_{i} & = t_{i - 1} + t_{i - 2}, \end{aligned}$

son “fuertemente” periódicos. El número de repeticiones en el string de Fibonacci $f_i$ , incluso comprimido con triples de Crochemore, es $O(f_n \log f_n)$ . El número de repeticiones primitivas también es $O(f_n \log f_n)$ .

Algoritmo de Main-Lorentz

La idea detrás del algoritmo de Main-Lorentz es divide y vencerás.

Parte el string inicial en mitades, y computa el número de repeticiones que yacen por completo en cada mitad mediante dos llamadas recursivas. Luego viene la parte difícil. El algoritmo encuentra todas las repeticiones que empiezan en la primera mitad y terminan en la segunda mitad (que llamaremos repeticiones cruzadas). Esta es la parte esencial del algoritmo de Main-Lorentz, y la discutiremos en detalle aquí.

La complejidad de los algoritmos de divide y vencerás está bien investigada. El teorema maestro dice que terminaremos con un algoritmo $O(n \log n)$ si podemos computar las repeticiones cruzadas en tiempo $O(n)$ .

Búsqueda de repeticiones cruzadas

Así, queremos encontrar todas las repeticiones que empiezan en la primera mitad del string, llamémosla $u$ , y terminan en la segunda mitad, llamémosla $v$ :

$s = u + v$

Sus longitudes son aproximadamente iguales a la longitud de $s$ dividida por dos.

Consideremos una repetición arbitraria y miremos el carácter del medio (más precisamente el primer carácter de la segunda mitad de la repetición). Es decir, si la repetición es una subcadena $s[i \dots j]$ , entonces el carácter del medio es $(i + j + 1) / 2$ .

Llamamos a una repetición izquierda o derecha según en qué string se ubica este carácter: en el string $u$ o en el string $v$ . En otras palabras, un string se llama izquierdo si la mayoría de él yace en $u$ ; de lo contrario lo llamamos derecho.

Discutiremos ahora cómo encontrar todas las repeticiones izquierdas. Encontrar todas las repeticiones derechas se puede hacer de la misma manera.

Denotemos la longitud de la repetición izquierda por $2l$ (es decir, cada mitad de la repetición tiene longitud $l$ ). Consideremos el primer carácter de la repetición que cae en el string $v$ (está en la posición $|u|$ del string $s$ ). Coincide con el carácter $l$ posiciones antes, denotemos esta posición $cntr$ .

Fijaremos esta posición $cntr$ , y buscaremos todas las repeticiones en esta posición $cntr$ .

Por ejemplo:

$c ~ \underset{cntr}{a} ~ c ~ | ~ a ~ d ~ a$

Las líneas verticales dividen las dos mitades. Aquí fijamos la posición $cntr = 1$ , y en esta posición encontramos la repetición $caca$ .

Está claro que si fijamos la posición $cntr$ , simultáneamente fijamos la longitud de las repeticiones posibles: $l = |u| - cntr$ . Una vez que sepamos cómo encontrar estas repeticiones, iteraremos sobre todos los valores posibles de $cntr$ de $0$ a $|u|-1$ , y encontraremos todas las repeticiones cruzadas izquierdas de longitud $l = |u|,~ |u|-1,~ \dots, 1$ .

Criterio para repeticiones cruzadas izquierdas

Ahora, ¿cómo podemos encontrar todas esas repeticiones para un $cntr$ fijado? Hay que tener en cuenta que todavía puede haber múltiples de tales repeticiones.

Miremos de nuevo una visualización, esta vez para la repetición $abcabc$ :

$\overbrace{a}^{l_1} ~ \overbrace{\underset{cntr}{b} ~ c}^{l_2} ~ \overbrace{a}^{l_1} ~ | ~ \overbrace{b ~ c}^{l_2}$

Aquí denotamos las longitudes de las dos piezas de la repetición con $l_1$ y $l_2$ : $l_1$ es la longitud de la repetición hasta la posición $cntr-1$ , y $l_2$ es la longitud de la repetición desde $cntr$ hasta el final de la mitad de la repetición. Tenemos $2l = l_1 + l_2 + l_1 + l_2$ como la longitud total de la repetición.

Generemos condiciones necesarias y suficientes para tal repetición en la posición $cntr$ de longitud $2l = 2(l_1 + l_2) = 2(|u| - cntr)$ :

Sea $k_1$ el mayor número tal que los primeros $k_1$ caracteres antes de la posición $cntr$ coinciden con los últimos $k_1$ caracteres del string $u$ :

$u[cntr - k_1 \dots cntr - 1] = u[|u| - k_1 \dots |u| - 1]$

Sea $k_2$ el mayor número tal que los $k_2$ caracteres que empiezan en la posición $cntr$ coinciden con los primeros $k_2$ caracteres del string $v$ :

$u [c n t r \dots c n t r + k_{2} - 1] = v [0 \dots k_{2} - 1]$

Entonces tenemos una repetición exactamente para cualquier par $(l_1,~ l_2)$ con

$\begin{aligned} l_{1} & \leq k_{1}, \\ l_{2} & \leq k_{2} . \end{aligned}$

Para resumir:

Fijamos una posición específica $cntr$ .
Todas las repeticiones que encontraremos ahora tienen longitud $2l = 2(|u| - cntr)$ . Puede haber múltiples de tales repeticiones; dependen de las longitudes $l_1$ y $l_2 = l - l_1$ .
Encontramos $k_1$ y $k_2$ como se describió arriba.
Entonces todas las repeticiones adecuadas son aquellas para las que las longitudes de las piezas $l_1$ y $l_2$ satisfacen las condiciones:

$\begin{aligned} l_{1} + l_{2} & = l = ∣ u ∣ - c n t r \\ l_{1} & \leq k_{1}, \\ l_{2} & \leq k_{2} . \end{aligned}$

Por lo tanto la única parte que queda es cómo podemos computar los valores $k_1$ y $k_2$ rápidamente para cada posición $cntr$ . Afortunadamente podemos computarlos en $O(1)$ usando la función Z:

Podemos encontrar el valor $k_1$ para cada posición calculando la función Z del string $\overline{u}$ (es decir, el string $u$ invertido). Entonces el valor $k_1$ para un $cntr$ particular será igual al valor correspondiente del arreglo de la función Z.
Para precomputar todos los valores $k_2$ , calculamos la función Z del string $v + # + u$ (es decir, el string $u$ concatenado con el carácter separador $#$ y el string $v$ ). De nuevo solo necesitamos consultar el valor correspondiente en la función Z para obtener el valor $k_2$ .

Así esto es suficiente para encontrar todas las repeticiones cruzadas izquierdas.

Repeticiones cruzadas derechas

Para computar las repeticiones cruzadas derechas actuamos de forma similar: definimos el centro $cntr$ como el carácter correspondiente al último carácter del string $u$ .

Entonces la longitud $k_1$ se definirá como el mayor número de caracteres antes de la posición $cntr$ (inclusive) que coinciden con los últimos caracteres del string $u$ . Y la longitud $k_2$ se definirá como el mayor número de caracteres que empiezan en $cntr + 1$ que coinciden con los caracteres del string $v$ .

Así podemos encontrar los valores $k_1$ y $k_2$ computando la función Z de los strings $\overline{u} + # + \overline{v}$ y $v$ .

Después de eso podemos encontrar las repeticiones mirando todas las posiciones $cntr$ , y usando el mismo criterio que teníamos para las repeticiones cruzadas izquierdas.

Implementación

La implementación del algoritmo de Main-Lorentz encuentra todas las repeticiones en forma de tuplas peculiares de tamaño cuatro: $(cntr,~ l,~ k_1,~ k_2)$ en tiempo $O(n \log n)$ . Si solo se quiere encontrar el número de repeticiones en un string, o solo se quiere encontrar la repetición más larga en un string, esta información es suficiente y el tiempo de ejecución seguirá siendo $O(n \log n)$ .

Nótese que si se quiere expandir estas tuplas para obtener la posición de inicio y de fin de cada repetición, entonces el tiempo de ejecución será $O(n^2)$ (recordemos que puede haber $O(n^2)$ repeticiones). En esta implementación lo haremos, y almacenaremos todas las repeticiones encontradas en un vector de pares de índices de inicio y fin.


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

int get_z(vector<int> const& z, int i) {
    if (0 <= i && i < (int)z.size())
        return z[i];
    else
        return 0;
}

vector<pair<int, int>> repetitions;

void convert_to_repetitions(int shift, bool left, int cntr, int l, int k1, int k2) {
    for (int l1 = max(1, l - k2); l1 <= min(l, k1); l1++) {
        if (left && l1 == l) break;
        int l2 = l - l1;
        int pos = shift + (left ? cntr - l1 : cntr - l - l1 + 1);
        repetitions.emplace_back(pos, pos + 2*l - 1);
    }
}

void find_repetitions(string s, int shift = 0) {
    int n = s.size();
    if (n == 1)
        return;

    int nu = n / 2;
    int nv = n - nu;
    string u = s.substr(0, nu);
    string v = s.substr(nu);
    string ru(u.rbegin(), u.rend());
    string rv(v.rbegin(), v.rend());

    find_repetitions(u, shift);
    find_repetitions(v, shift + nu);

    vector<int> z1 = z_function(ru);
    vector<int> z2 = z_function(v + '#' + u);
    vector<int> z3 = z_function(ru + '#' + rv);
    vector<int> z4 = z_function(v);

    for (int cntr = 0; cntr < n; cntr++) {
        int l, k1, k2;
        if (cntr < nu) {
            l = nu - cntr;
            k1 = get_z(z1, nu - cntr);
            k2 = get_z(z2, nv + 1 + cntr);
        } else {
            l = cntr - nu + 1;
            k1 = get_z(z3, nu + 1 + nv - 1 - (cntr - nu));
            k2 = get_z(z4, (cntr - nu) + 1);
        }
        if (k1 + k2 >= l)
            convert_to_repetitions(shift, cntr < nu, cntr, l, k1, k2);
    }
}