Factorización de Lyndon

Factorización de Lyndon

Primero definamos la noción de factorización de Lyndon.

Un string se llama simple (o palabra de Lyndon), si es estrictamente más pequeño que cualquiera de sus propios sufijos no triviales. Ejemplos de strings simples son: $a$, $b$, $ab$, $aab$, $abb$, $ababb$, $abcd$. Se puede mostrar que un string es simple si y solo si es estrictamente más pequeño que todos sus desplazamientos cíclicos no triviales.

A continuación, sea $s$ un string dado. La factorización de Lyndon del string $s$ es una factorización $s = w_1 w_2 \dots w_k$, donde todos los strings $w_i$ son simples, y están en orden no creciente $w_1 \ge w_2 \ge \dots \ge w_k$.

Se puede mostrar que para cualquier string tal factorización existe y que es única.

Algoritmo de Duval

El algoritmo de Duval construye la factorización de Lyndon en tiempo $O(n)$ usando $O(1)$ de memoria adicional.

Primero introduzcamos otra noción: un string $t$ se llama pre-simple, si tiene la forma $t = w w \dots w \overline{w}$, donde $w$ es un string simple y $\overline{w}$ es un prefijo de $w$ (posiblemente vacío). Un string simple también es pre-simple.

El algoritmo de Duval es voraz. En cualquier punto de su ejecución, el string $s$ estará de hecho dividido en tres strings $s = s_1 s_2 s_3$, donde la factorización de Lyndon de $s_1$ ya se encontró y está finalizada, el string $s_2$ es pre-simple (y conocemos la longitud del string simple en él), y $s_3$ está completamente sin tocar. En cada iteración el algoritmo de Duval toma el primer carácter del string $s_3$ e intenta agregarlo al string $s_2$. Si $s_2$ deja de ser pre-simple, entonces la factorización de Lyndon de alguna parte de $s_2$ se vuelve conocida, y esa parte pasa a $s_1$.

Describamos el algoritmo con más detalle. El puntero $i$ siempre apuntará al comienzo del string $s_2$. El bucle externo se ejecutará mientras $i < n$. Dentro del bucle usamos dos punteros adicionales, $j$ que apunta al comienzo de $s_3$, y $k$ que apunta al carácter actual con el que estamos comparando. Queremos agregar el carácter $s[j]$ al string $s_2$, lo que requiere una comparación con el carácter $s[k]$. Puede haber tres casos distintos:

• $s[j] = s[k]$: si este es el caso, entonces agregar el símbolo $s[j]$ a $s_2$ no viola su pre-simplicidad. Así que simplemente incrementamos los punteros $j$ y $k$.
• $s[j] > s[k]$: aquí, el string $s_2 + s[j]$ se vuelve simple. Podemos incrementar $j$ y resetear $k$ al comienzo de $s_2$, de modo que el siguiente carácter se pueda comparar con el comienzo de la palabra simple.
• $s[j] < s[k]$: el string $s_2 + s[j]$ ya no es pre-simple. Por lo tanto partiremos el string pre-simple $s_2$ en sus strings simples y el resto, posiblemente vacío. El string simple tendrá longitud $j - k$. En la siguiente iteración empezamos de nuevo con el $s_2$ restante.

Implementación

Aquí presentamos la implementación del algoritmo de Duval, que devolverá la factorización de Lyndon deseada de un string dado $s$.

vector<string> duval(string const& s) {
    int n = s.size();
    int i = 0;
    vector<string> factorization;
    while (i < n) {
        int j = i + 1, k = i;
        while (j < n && s[k] <= s[j]) {
            if (s[k] < s[j])
                k = i;
            else
                k++;
            j++;
        }
        while (i <= k) {
            factorization.push_back(s.substr(i, j - k));
            i += j - k;
        }
    }
    return factorization;
}

Complejidad

Estimemos el tiempo de ejecución de este algoritmo.

El bucle while externo no supera $n$ iteraciones, ya que al final de cada iteración $i$ aumenta. También el segundo bucle while interno corre en $O(n)$, ya que solo emite la factorización final.

Así que solo nos interesa el primer bucle while interno. ¿Cuántas iteraciones realiza en el peor caso? Es fácil ver que las palabras simples que identificamos en cada iteración del bucle externo son más largas que el resto que comparamos adicionalmente. Por lo tanto también la suma de los restos será menor que $n$, lo que significa que solo realizamos a lo sumo $O(n)$ iteraciones del primer bucle while interno. De hecho el número total de comparaciones de caracteres no superará $4n - 3$.

Encontrar el desplazamiento cíclico más pequeño

Sea $s$ un string. Construimos la factorización de Lyndon del string $s + s$ (en tiempo $O(n)$). Buscaremos un string simple en la factorización que empiece en una posición menor que $n$ (es decir, empieza en la primera instancia de $s$), y termine en una posición mayor o igual que $n$ (es decir, en la segunda instancia de $s$). Se afirma que la posición de inicio de este string simple será el comienzo del desplazamiento cíclico más pequeño deseado. Esto se puede verificar fácilmente usando la definición de la descomposición de Lyndon.

El comienzo del bloque simple se puede encontrar fácilmente: basta con recordar el puntero $i$ al comienzo de cada iteración del bucle externo, que indicaba el comienzo del string pre-simple actual.

Así obtenemos la siguiente implementación:

string min_cyclic_string(string s) {
    s += s;
    int n = s.size();
    int i = 0, ans = 0;
    while (i < n / 2) {
        ans = i;
        int j = i + 1, k = i;
        while (j < n && s[k] <= s[j]) {
            if (s[k] < s[j])
                k = i;
            else
                k++;
            j++;
        }
        while (i <= k)
            i += j - k;
    }
    return s.substr(ans, n / 2);
}

Problemas

• UVA #719 - Glass Beads