Arreglo de sufijos

Definición

Sea $s$ un string de longitud $n$ . El $i$ -ésimo sufijo de $s$ es la subcadena $s[i \ldots n - 1]$ .

Un arreglo de sufijos (suffix array) contendrá enteros que representan los índices de inicio de todos los sufijos de un string dado, después de que dichos sufijos se hayan ordenado.

Como ejemplo, miremos el string $s = abaab$ . Todos los sufijos son los siguientes

$\begin{array}{ll} 0. & a b a a b \\ 1. & b a a b \\ 2. & a a b \\ 3. & a b \\ 4. & b \end{array}$

& baab \
& aab \
& ab \
& b \end{array} $0. 1. 2. 3. 4. am p; abaab am p; baab am p; aab am p; ab am p; b$ $0. 1. 2. 3. 4. abaab baab aab ab b$

Después de ordenar estos strings:

$\begin{array}{ll} 2. & a a b \\ 3. & a b \\ 0. & a b a a b \\ 4. & b \\ 1. & b a a b \end{array}$

& baab \end{array} $2. 3. 0. 4. 1. am p; aab am p; ab am p; abaab am p; b am p; baab$ $2. 3. 0. 4. 1. aab ab abaab b baab$

Por lo tanto el arreglo de sufijos de $s$ será $(2,~ 3,~ 0,~ 4,~ 1)$ .

Como estructura de datos se usa ampliamente en áreas como compresión de datos, bioinformática y, en general, en cualquier área que trate con strings y problemas de matching de strings.

Construcción

Enfoque $O(n^2 \log n)$ {data-toc-label=“Enfoque O(n^2 log n)”}

Este es el enfoque más naive. Obtener todos los sufijos y ordenarlos usando quicksort o mergesort, reteniendo simultáneamente sus índices originales. El ordenamiento usa $O(n \log n)$ comparaciones, y como comparar dos strings tomará adicionalmente $O(n)$ de tiempo, obtenemos la complejidad final $O(n^2 \log n)$ .

Enfoque $O(n \log n)$ {data-toc-label=“Enfoque O(n log n)”}

Estrictamente hablando, el siguiente algoritmo no ordenará los sufijos, sino más bien los desplazamientos cíclicos de un string. Sin embargo, de él podemos derivar muy fácilmente un algoritmo para ordenar sufijos: basta con agregar al final del string un carácter arbitrario que sea más pequeño que cualquier carácter del string. Es común usar el símbolo <span class=“katex-display”> $. Entonces el orden de los desplazamientos cíclicos ordenados es equivalente al orden de los sufijos ordenados, como se muestra aquí con el string$ dabbb$.

$\begin{array}{lll}$

& abbb<span class=“katex-error” title=“ParseError: KaTeX parse error: Expected ‘EOF’, got ’&’ at position 3: d &̲amp; abbb \ 4.…” style=“color:#cc0000”>d & abbb \
& b</span>dabb & b \
& bb<span class=“katex-error” title=“ParseError: KaTeX parse error: Expected ‘EOF’, got ’&’ at position 5: dab &̲amp; bb \
&…” style=“color:#cc0000”>dab & bb \
& bbb</span>da & bbb \
& dabbb$ & dabbb \end{array} $1. 4. 3. 2. 0. abbb $ d b $ d abb bb $ d ab bbb $ d a d abbb $ abbb b bb bbb d abbb$

Como vamos a ordenar desplazamientos cíclicos, consideraremos subcadenas cíclicas. Usaremos la notación $s[i \dots j]$ para la subcadena de $s$ incluso si $i > j$ . En este caso en realidad nos referimos al string $s[i \dots n-1] + s[0 \dots j]$ . Además tomaremos todos los índices módulo la longitud de $s$ , y omitiremos la operación módulo por simplicidad.

El algoritmo que discutimos realizará $\lceil \log n \rceil + 1$ iteraciones. En la $k$ -ésima iteración ( $k = 0 \dots \lceil \log n \rceil$ ) ordenamos las $n$ subcadenas cíclicas de $s$ de longitud $2^k$ . Después de la $\lceil \log n \rceil$ -ésima iteración las subcadenas de longitud $2^{\lceil \log n \rceil} \ge n$ estarán ordenadas, así que esto es equivalente a ordenar los desplazamientos cíclicos por completo.

En cada iteración del algoritmo, además de la permutación $p[0 \dots n-1]$ , donde $p[i]$ es el índice de la $i$ -ésima subcadena (que empieza en $i$ y tiene longitud $2^k$ ) en el orden ordenado, también mantendremos un arreglo $c[0 \dots n-1]$ , donde $c[i]$ corresponde a la clase de equivalencia a la que pertenece la subcadena. Porque algunas de las subcadenas serán idénticas, y el algoritmo necesita tratarlas de igual forma. Por conveniencia las clases se etiquetarán con números empezando desde cero. Además los números $c[i]$ se asignarán de forma que preserven información sobre el orden: si una subcadena es más pequeña que la otra, entonces también debería tener una etiqueta de clase más pequeña. El número de clases de equivalencia se almacenará en una variable $\text{classes}$ .

Miremos un ejemplo. Consideremos el string $s = aaba$ . Las subcadenas cíclicas y los arreglos correspondientes $p[]$ y $c[]$ se dan para cada iteración:

$\begin{array}{cccc} 0 : & (a, a, b, a) & p = (0, 1, 3, 2) & c = (0, 0, 1, 0) \\ 1 : & (a a, a b, b a, a a) & p = (0, 3, 1, 2) & c = (0, 1, 2, 0) \\ 2 : & (a a b a, a b a a, b a a a, a a a b) & p = (3, 0, 1, 2) & c = (1, 2, 3, 0) \end{array}$

Cabe notar que los valores de $p[]$ pueden ser distintos. Por ejemplo en la iteración $0$ -ésima el arreglo también podría ser $p = (3,~ 1,~ 0,~ 2)$ o $p = (3,~ 0,~ 1,~ 2)$ . Todas estas opciones permutan las subcadenas a un orden ordenado. Así que todas son válidas. Al mismo tiempo el arreglo $c[]$ es fijo: no puede haber ambigüedades.

Enfoquémonos ahora en la implementación del algoritmo. Escribiremos una función que toma un string $s$ y devuelve las permutaciones de los desplazamientos cíclicos ordenados.


vector<int> sort_cyclic_shifts(string const& s) {
    int n = s.size();
    const int alphabet = 256;

Al comienzo (en la iteración $0$ -ésima) debemos ordenar las subcadenas cíclicas de longitud $1$ , es decir, tenemos que ordenar todos los caracteres del string y dividirlos en clases de equivalencia (los mismos símbolos se asignan a la misma clase). Esto se puede hacer de forma trivial, por ejemplo, usando ordenamiento por conteo. Para cada carácter contamos cuántas veces aparece en el string, y luego usamos esta información para crear el arreglo $p[]$ . Después recorremos el arreglo $p[]$ y construimos $c[]$ comparando caracteres adyacentes.


    vector<int> p(n), c(n), cnt(max(alphabet, n), 0);
    for (int i = 0; i < n; i++)
        cnt[s[i]]++;
    for (int i = 1; i < alphabet; i++)
        cnt[i] += cnt[i-1];
    for (int i = 0; i < n; i++)
        p[--cnt[s[i]]] = i;
    c[p[0]] = 0;
    int classes = 1;
    for (int i = 1; i < n; i++) {
        if (s[p[i]] != s[p[i-1]])
            classes++;
        c[p[i]] = classes - 1;
    }

Ahora tenemos que hablar del paso de iteración. Asumamos que ya realizamos el paso $k-1$ -ésimo y calculamos los valores de los arreglos $p[]$ y $c[]$ para él. Queremos calcular los valores del paso $k$ -ésimo en tiempo $O(n)$ . Como realizamos este paso $O(\log n)$ veces, el algoritmo completo tendrá una complejidad temporal de $O(n \log n)$ .

Para ello, nótese que las subcadenas cíclicas de longitud $2^k$ consisten en dos subcadenas de longitud $2^{k-1}$ que podemos comparar entre sí en $O(1)$ usando la información de la fase anterior — los valores de las clases de equivalencia $c[]$ . Así, para dos subcadenas de longitud $2^k$ que empiezan en las posiciones $i$ y $j$ , toda la información necesaria para compararlas está contenida en los pares $(c[i],~ c[i + 2^{k-1}])$ y $(c[j],~ c[j + 2^{k-1}])$ .

$\dots \overbrace{ \underbrace{s_i \dots s_{i+2^{k-1}-1}}$

Esto nos da una solución muy simple: ordenar las subcadenas de longitud $2^k$ por estos pares de números. Esto nos dará el orden requerido $p[]$ . Sin embargo un ordenamiento normal corre en tiempo $O(n \log n)$ , con lo cual no estamos satisfechos. Esto solo nos daría un algoritmo para construir un arreglo de sufijos en tiempo $O(n \log^2 n)$ .

¿Cómo realizamos rápidamente tal ordenamiento de los pares? Como los elementos de los pares no superan $n$ , podemos usar de nuevo ordenamiento por conteo. Sin embargo ordenar pares con ordenamiento por conteo no es lo más eficiente. Para lograr una mejor constante oculta en la complejidad, usaremos otro truco.

Usamos aquí la técnica en la que se basa el radix sort: para ordenar los pares primero los ordenamos por el segundo elemento, y luego por el primer elemento (con un ordenamiento estable, es decir, un ordenamiento que no rompe el orden relativo de elementos iguales). Sin embargo los segundos elementos ya estaban ordenados en la iteración anterior. Así, para ordenar los pares por los segundos elementos, solo necesitamos restar $2^{k-1}$ a los índices en $p[]$ (p. ej. si la subcadena más pequeña de longitud $2^{k-1}$ empieza en la posición $i$ , entonces la subcadena de longitud $2^k$ con la segunda mitad más pequeña empieza en $i - 2^{k-1}$ ).

Así, solo con restas simples podemos ordenar los segundos elementos de los pares en $p[]$ . Ahora necesitamos realizar un ordenamiento estable por los primeros elementos. Como ya se mencionó, esto se puede lograr con ordenamiento por conteo.

Lo único que queda es calcular las clases de equivalencia $c[]$ , pero como antes esto se puede hacer simplemente iterando sobre la permutación ordenada $p[]$ y comparando pares vecinos.

Aquí está el resto de la implementación. Usamos arreglos temporales $pn[]$ y $cn[]$ para almacenar la permutación por los segundos elementos y los nuevos índices de clase de equivalencia.


    vector<int> pn(n), cn(n);
    for (int h = 0; (1 << h) < n; ++h) {
        for (int i = 0; i < n; i++) {
            pn[i] = p[i] - (1 << h);
            if (pn[i] < 0)
                pn[i] += n;
        }
        fill(cnt.begin(), cnt.begin() + classes, 0);
        for (int i = 0; i < n; i++)
            cnt[c[pn[i]]]++;
        for (int i = 1; i < classes; i++)
            cnt[i] += cnt[i-1];
        for (int i = n-1; i >= 0; i--)
            p[--cnt[c[pn[i]]]] = pn[i];
        cn[p[0]] = 0;
        classes = 1;
        for (int i = 1; i < n; i++) {
            pair<int, int> cur = {c[p[i]], c[(p[i] + (1 << h)) % n]};
            pair<int, int> prev = {c[p[i-1]], c[(p[i-1] + (1 << h)) % n]};
            if (cur != prev)
                ++classes;
            cn[p[i]] = classes - 1;
        }
        c.swap(cn);
    }
    return p;
}

El algoritmo requiere $O(n \log n)$ de tiempo y $O(n)$ de memoria. Por simplicidad usamos el rango ASCII completo como alfabeto.

Si se sabe que el string solo contiene un subconjunto de caracteres, p. ej. solo letras minúsculas, entonces la implementación se puede optimizar, pero el factor de optimización probablemente sería insignificante, ya que el tamaño del alfabeto solo importa en la primera iteración. Toda otra iteración depende del número de clases de equivalencia, que puede alcanzar rápidamente $O(n)$ incluso si inicialmente era un string sobre un alfabeto de tamaño $2$ .

Nótese también que este algoritmo solo ordena los desplazamientos cíclicos. Como se mencionó al comienzo de esta sección, podemos generar el orden ordenado de los sufijos agregando un carácter más pequeño que todos los demás caracteres del string, y ordenando el string resultante por desplazamientos cíclicos, p. ej. ordenando los desplazamientos cíclicos de $. Esto obviamente dará el arreglo de sufijos de$


vector<int> suffix_array_construction(string s) {
    s += "$";
    vector<int> sorted_shifts = sort_cyclic_shifts(s);
    sorted_shifts.erase(sorted_shifts.begin());
    return sorted_shifts;
}

Aplicaciones

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

El algoritmo de arriba ordena todos los desplazamientos cíclicos (sin agregar un carácter al string), y por lo tanto $p[0]$ da la posición del desplazamiento cíclico más pequeño.

Encontrar una subcadena en un string

La tarea es encontrar un string $s$ dentro de algún texto $t$ de forma online: conocemos el texto $t$ de antemano, pero no el string $s$ . Podemos crear el arreglo de sufijos del texto $t$ en tiempo $O(|t| \log |t|)$ . Ahora podemos buscar la subcadena $s$ de la siguiente manera. La ocurrencia de $s$ debe ser un prefijo de algún sufijo de $t$ . Como ordenamos todos los sufijos, podemos realizar una búsqueda binaria de $s$ en $p$ . Comparar el sufijo actual y la subcadena $s$ dentro de la búsqueda binaria se puede hacer en tiempo $O(|s|)$ , por lo tanto la complejidad para encontrar la subcadena es $O(|s| \log |t|)$ . Nótese también que si la subcadena ocurre múltiples veces en $t$ , entonces todas las ocurrencias estarán unas al lado de otras en $p$ . Por lo tanto el número de ocurrencias se puede encontrar con una segunda búsqueda binaria, y todas las ocurrencias se pueden imprimir fácilmente.

Comparar dos subcadenas de un string

Queremos poder comparar dos subcadenas de la misma longitud de un string dado $s$ en tiempo $O(1)$ , es decir, comprobar si la primera subcadena es más pequeña que la segunda.

Para ello construimos el arreglo de sufijos en tiempo $O(|s| \log |s|)$ y almacenamos todos los resultados intermedios de las clases de equivalencia $c[]$ .

Usando esta información podemos comparar cualesquiera dos subcadenas cuya longitud sea una potencia de dos en O(1): para ello basta con comparar las clases de equivalencia de ambas subcadenas. Ahora queremos generalizar este método a subcadenas de longitud arbitraria.

Comparemos dos subcadenas de longitud $l$ con índices de inicio $i$ y $j$ . Encontramos la mayor longitud de un bloque que cabe dentro de una subcadena de esta longitud: el mayor $k$ tal que $2^k \le l$ . Entonces comparar las dos subcadenas se puede reemplazar por comparar dos bloques superpuestos de longitud $2^k$ : primero hay que comparar los dos bloques que empiezan en $i$ y $j$ , y si estos son iguales entonces comparar los dos bloques que terminan en las posiciones $i + l - 1$ y $j + l - 1$ :

$\dots \overbrace{\underbrace{s_i \dots s_{i+l-2^k} \dots s_{i+2^k-1}}$

$\dots \overbrace{s_i \dots \underbrace{s_{i+l-2^k} \dots s_{i+2^k-1} \dots s_{i+l-1}}$

Aquí está la implementación de la comparación. Nótese que se asume que la función se llama con el $k$ ya calculado. $k$ se puede computar con $\lfloor \log l \rfloor$ , pero es más eficiente precomputar todos los valores de $k$ para cada $l$ . Véase por ejemplo el artículo sobre la Tabla Dispersa, que usa una idea similar y computa todos los valores de $\log$ .


int compare(int i, int j, int l, int k) {
    pair<int, int> a = {c[k][i], c[k][(i+l-(1 << k))%n]};
    pair<int, int> b = {c[k][j], c[k][(j+l-(1 << k))%n]};
    return a == b ? 0 : a < b ? -1 : 1;
}

Prefijo común más largo de dos subcadenas con memoria adicional

Para un string dado $s$ queremos computar el prefijo común más largo (LCP) de dos sufijos arbitrarios con posiciones $i$ y $j$ .

El método descrito aquí usa $O(|s| \log |s|)$ de memoria adicional. Un enfoque completamente distinto que solo usará una cantidad lineal de memoria se describe en la siguiente sección.

Construimos el arreglo de sufijos en tiempo $O(|s| \log |s|)$ , y recordamos los resultados intermedios de los arreglos $c[]$ de cada iteración.

Calculemos el LCP de dos sufijos que empiezan en $i$ y $j$ . Podemos comparar cualesquiera dos subcadenas con una longitud igual a una potencia de dos en $O(1)$ . Para ello, comparamos los strings por potencias de dos (de la potencia más alta a la más baja) y si las subcadenas de esta longitud son iguales, entonces agregamos la longitud igual a la respuesta y continuamos comprobando el LCP a la derecha de la parte igual, es decir, a $i$ y $j$ se les suma la potencia de dos actual.


int lcp(int i, int j) {
    int ans = 0;
    for (int k = log_n; k >= 0; k--) {
        if (c[k][i % n] == c[k][j % n]) {
            ans += 1 << k;
            i += 1 << k;
            j += 1 << k;
        }
    }
    return ans;
}

Aquí log_n denota una constante igual al logaritmo de $n$ en base $2$ redondeado hacia abajo.

Prefijo común más largo de dos subcadenas sin memoria adicional

Tenemos la misma tarea que en la sección anterior. Tenemos que computar el prefijo común más largo (LCP) de dos sufijos de un string $s$ .

A diferencia del método anterior, este solo usará $O(|s|)$ de memoria. El resultado del preprocesamiento será un arreglo (que a su vez es una fuente importante de información sobre el string, y por lo tanto también se usa para resolver otras tareas). Las consultas LCP se pueden responder realizando consultas RMQ (consultas de mínimo en un rango) en este arreglo, así que para distintas implementaciones es posible alcanzar tiempo logarítmico e incluso constante por consulta.

La base de este algoritmo es la siguiente idea: computaremos el prefijo común más largo para cada par de sufijos adyacentes en el orden ordenado. En otras palabras construimos un arreglo $\text{lcp}[0 \dots n-2]$ , donde $\text{lcp}[i]$ es igual a la longitud del prefijo común más largo de los sufijos que empiezan en $p[i]$ y $p[i+1]$ . Este arreglo nos dará una respuesta para cualesquiera dos sufijos adyacentes del string. Luego la respuesta para dos sufijos arbitrarios, no necesariamente vecinos, se puede obtener de este arreglo. De hecho, sea la solicitud computar el LCP de los sufijos $p[i]$ y $p[j]$ . Entonces la respuesta a esta consulta será $\min(lcp[i],~ lcp[i+1],~ \dots,~ lcp[j-1])$ .

Así, si tenemos tal arreglo $\text{lcp}$ , entonces el problema se reduce al RMQ, que tiene un gran número de soluciones distintas con distintas complejidades.

Así que la tarea principal es construir este arreglo $\text{lcp}$ . Usaremos el algoritmo de Kasai, que puede computar este arreglo en tiempo $O(n)$ .

Miremos dos sufijos adyacentes en el orden ordenado (orden del arreglo de sufijos). Sean sus posiciones de inicio $i$ y $j$ y su $\text{lcp}$ igual a $k > 0$ . Si quitamos la primera letra de ambos sufijos — es decir, tomamos los sufijos $i+1$ y $j+1$ — entonces debería ser obvio que el $\text{lcp}$ de estos dos es $k - 1$ . Sin embargo no podemos usar este valor y escribirlo en el arreglo $\text{lcp}$ , porque estos dos sufijos podrían no estar uno al lado del otro en el orden ordenado. El sufijo $i+1$ será por supuesto más pequeño que el sufijo $j+1$ , pero podría haber algunos sufijos entre ellos. Sin embargo, como sabemos que el LCP entre dos sufijos es el valor mínimo de todas las transiciones, también sabemos que el LCP entre cualquier par en ese intervalo tiene que ser al menos $k-1$ , especialmente también entre $i+1$ y el siguiente sufijo. Y posiblemente puede ser más grande.

Ahora ya podemos implementar el algoritmo. Iteraremos sobre los sufijos en orden de su longitud. De esta forma podemos reutilizar el último valor $k$ , ya que pasar del sufijo $i$ al sufijo $i+1$ es exactamente lo mismo que quitar la primera letra. Necesitaremos un arreglo adicional $\text{rank}$ , que nos dará la posición de un sufijo en la lista ordenada de sufijos.


vector<int> lcp_construction(string const& s, vector<int> const& p) {
    int n = s.size();
    vector<int> rank(n, 0);
    for (int i = 0; i < n; i++)
        rank[p[i]] = i;

    int k = 0;
    vector<int> lcp(n-1, 0);
    for (int i = 0; i < n; i++) {
        if (rank[i] == n - 1) {
            k = 0;
            continue;
        }
        int j = p[rank[i] + 1];
        while (i + k < n && j + k < n && s[i+k] == s[j+k])
            k++;
        lcp[rank[i]] = k;
        if (k)
            k--;
    }
    return lcp;
}

Es fácil ver que disminuimos $k$ a lo sumo $O(n)$ veces (en cada iteración a lo sumo una vez, excepto para $\text{rank}[i] == n-1$ , donde lo reseteamos directamente a $0$ ), y el LCP entre dos strings es a lo sumo $n-1$ , también incrementaremos $k$ solo $O(n)$ veces. Por lo tanto el algoritmo corre en tiempo $O(n)$ .

Número de subcadenas distintas

Preprocesamos el string $s$ computando el arreglo de sufijos y el arreglo LCP. Usando esta información podemos computar el número de subcadenas distintas en el string.

Para ello, pensaremos en qué nuevas subcadenas empiezan en la posición $p[0]$ , luego en $p[1]$ , etc. De hecho tomamos los sufijos en orden ordenado y vemos qué prefijos dan nuevas subcadenas. Así no pasaremos por alto ninguna por accidente.

Como los sufijos están ordenados, es claro que el sufijo actual $p[i]$ dará nuevas subcadenas para todos sus prefijos, excepto para los prefijos que coinciden con el sufijo $p[i-1]$ . Así, todos sus prefijos excepto los primeros $\text{lcp}[i-1]$ . Como la longitud del sufijo actual es $n - p[i]$ , $n - p[i] - \text{lcp}[i-1]$ prefijos nuevos empiezan en $p[i]$ . Sumando sobre todos los sufijos, obtenemos la respuesta final:

$\sum_{i=0}^{n-1} (n - p[i]) - \sum_{i=0}^{n-2} \text{lcp}[i] = \frac{n^2 + n}{2} - \sum_{i=0}^{n-2} \text{lcp}[i]$