Autómata de sufijos

Un autómata de sufijos (suffix automaton) es una estructura de datos poderosa que permite resolver muchos problemas relacionados con strings.

Por ejemplo, se puede buscar todas las ocurrencias de un string en otro, o contar la cantidad de subcadenas distintas de un string dado. Ambas tareas se pueden resolver en tiempo lineal con ayuda de un autómata de sufijos.

Intuitivamente, un autómata de sufijos se puede entender como una forma comprimida de todas las subcadenas de un string dado. Un hecho impresionante es que el autómata de sufijos contiene toda esta información en una forma altamente comprimida. Para un string de longitud $n$ solo requiere memoria $O(n)$. Además, también se puede construir en tiempo $O(n)$ (si consideramos el tamaño $k$ del alfabeto como una constante); en caso contrario tanto la memoria como la complejidad temporal serán $O(n \log k)$.

La linealidad del tamaño del autómata de sufijos fue descubierta primero en 1983 por Blumer et al., y en 1985 se presentaron los primeros algoritmos lineales de construcción por Crochemore y Blumer.

Definición de un autómata de sufijos

Un autómata de sufijos para un string dado $s$ es un DFA mínimo (autómata finito determinista / máquina de estados finitos determinista) que acepta todos los sufijos del string $s$.

En otras palabras:

• Un autómata de sufijos es un grafo acíclico orientado. Los vértices se llaman estados, y las aristas se llaman transiciones entre estados.
• Uno de los estados $t_0$ es el estado inicial, y debe ser la fuente del grafo (todos los demás estados son alcanzables desde $t_0$).
• Cada transición está etiquetada con algún carácter. Todas las transiciones que salen de un estado deben tener etiquetas distintas.
• Uno o varios estados se marcan como estados terminales. Si empezamos desde el estado inicial $t_0$ y nos movemos a lo largo de transiciones hasta un estado terminal, entonces las etiquetas de las transiciones recorridas deben deletrear uno de los sufijos del string $s$. Cada uno de los sufijos de $s$ debe poder deletrearse usando un camino de $t_0$ a un estado terminal.
• El autómata de sufijos contiene el mínimo número de vértices entre todos los autómatas que satisfacen las condiciones descritas arriba.

Propiedad de las subcadenas

La propiedad más simple e importante de un autómata de sufijos es que contiene información sobre todas las subcadenas del string $s$. Cualquier camino que empieza en el estado inicial $t_0$, si escribimos las etiquetas de las transiciones, forma una subcadena de $s$. Y recíprocamente, cada subcadena de $s$ corresponde a un cierto camino que empieza en $t_0$.

Para simplificar las explicaciones, diremos que la subcadena corresponde a ese camino (empezando en $t_0$ y las etiquetas deletrean la subcadena). Y recíprocamente decimos que cualquier camino corresponde al string deletreado por sus etiquetas.

Uno o varios caminos pueden llevar a un estado. Así, diremos que un estado corresponde al conjunto de strings que corresponden a estos caminos.

Ejemplos de autómatas de sufijos construidos

Aquí mostraremos algunos ejemplos de autómatas de sufijos para varios strings simples.

Denotaremos el estado inicial con azul y los estados terminales con verde.

Para el string $s =~ \text{""}$:

Para el string $s =~ \text{“a”}$:

Para el string $s =~ \text{“aa”}$:

Para el string $s =~ \text{“ab”}$:

Para el string $s =~ \text{“aba”}$:

Para el string $s =~ \text{“abb”}$:

Para el string $s =~ \text{“abbb”}$:

Construcción en tiempo lineal

Antes de describir el algoritmo para construir un autómata de sufijos en tiempo lineal, necesitamos introducir varios conceptos nuevos y demostraciones simples, que serán muy importantes para entender la construcción.

Posiciones finales $endpos$ {data-toc-label=“Posiciones finales”}

Consideremos cualquier subcadena no vacía $t$ del string $s$. Denotaremos con $endpos(t)$ el conjunto de todas las posiciones en el string $s$ en las que terminan las ocurrencias de $t$. Por ejemplo, tenemos $endpos(\text{“bc”}) = {2, 4}$ para el string $\text{“abcbc”}$.

Llamaremos a dos subcadenas $t_1$ y $t_2$ $endpos$-equivalentes si sus conjuntos de finales coinciden: $endpos(t_1) = endpos(t_2)$. Así, todas las subcadenas no vacías del string $s$ se pueden descomponer en varias clases de equivalencia según sus conjuntos $endpos$.

Resulta que en una máquina de sufijos las subcadenas $endpos$-equivalentes corresponden al mismo estado. En otras palabras, el número de estados en un autómata de sufijos es igual al número de clases de equivalencia entre todas las subcadenas, más el estado inicial. Cada estado de un autómata de sufijos corresponde a una o más subcadenas que tienen el mismo valor $endpos$.

Más adelante describiremos el algoritmo de construcción usando esta hipótesis. Luego veremos que se cumplen todas las propiedades requeridas de un autómata de sufijos, excepto la minimalidad. Y la minimalidad se sigue del teorema de Nerode (que no se demostrará en este artículo).

Podemos hacer algunas observaciones importantes respecto de los valores $endpos$:

Lema 1: Dos subcadenas no vacías $u$ y $w$ (con $length(u) \le length(w)$) son $endpos$-equivalentes si y solo si el string $u$ ocurre en $s$ solo en forma de sufijo de $w$.

La demostración es obvia. Si $u$ y $w$ tienen los mismos valores $endpos$, entonces $u$ es un sufijo de $w$ y aparece solo en forma de sufijo de $w$ en $s$. Y si $u$ es un sufijo de $w$ y aparece solo en forma de sufijo en $s$, entonces los valores $endpos$ son iguales por definición.

Lema 2: Consideremos dos subcadenas no vacías $u$ y $w$ (con $length(u) \le length(w)$). Entonces sus conjuntos $endpos$ o bien no se intersectan en absoluto, o $endpos(w)$ es un subconjunto de $endpos(u)$. Y depende de si $u$ es un sufijo de $w$ o no.

$$\{\begin{array}{ll}endpos(w)\subseteq endpos(u)& \text{if }u\text{ is a suffix of }w\\ \\ endpos(w)\cap endpos(u)=\mathrm{\varnothing }& \text{otherwise}\end{array}$$$$\begin{cases} endpos(w) \subseteq endpos(u) & \text{if } u \text{ is a suffix of } w \\ endpos(w) \cap endpos(u) = \emptyset & \text{otherwise} \end{cases}$$

Demostración: Si los conjuntos $endpos(u)$ y $endpos(w)$ tienen al menos un elemento en común, entonces los strings $u$ y $w$ ambos terminan en esa posición, es decir, $u$ es un sufijo de $w$. Pero entonces en cada ocurrencia de $w$ también aparece la subcadena $u$, lo que significa que $endpos(w)$ es un subconjunto de $endpos(u)$.

Lema 3: Consideremos una clase de $endpos$-equivalencia. Ordenemos todas las subcadenas de esta clase por longitud decreciente. Entonces en la secuencia resultante cada subcadena será una más corta que la anterior, y al mismo tiempo será un sufijo de la anterior. En otras palabras, en una misma clase de equivalencia, las subcadenas más cortas son de hecho sufijos de las subcadenas más largas, y toman todas las longitudes posibles en un cierto intervalo $[x; y]$.

Demostración: Fijemos alguna clase de $endpos$-equivalencia. Si solo contiene un string, entonces el lema es obviamente cierto. Ahora digamos que el número de strings en la clase es mayor que uno.

Según el Lema 1, dos strings $endpos$-equivalentes distintos están siempre de tal forma que el más corto es un sufijo propio del más largo. En consecuencia, no puede haber dos strings de la misma longitud en la clase de equivalencia.

Denotemos por $w$ el más largo, y por $u$ el string más corto de la clase de equivalencia. Según el Lema 1, el string $u$ es un sufijo propio del string $w$. Consideremos ahora cualquier sufijo de $w$ con una longitud en el intervalo $[length(u); length(w)]$. Es fácil ver que este sufijo también está contenido en la misma clase de equivalencia. Porque este sufijo solo puede aparecer en forma de sufijo de $w$ en el string $s$ (ya que también el sufijo más corto $u$ ocurre en $s$ solo en forma de sufijo de $w$). En consecuencia, según el Lema 1, este sufijo es $endpos$-equivalente al string $w$.

Enlaces de sufijo $link$ {data-toc-label=“Enlaces de sufijo”}

Consideremos algún estado $v \ne t_0$ en el autómata. Como sabemos, el estado $v$ corresponde a la clase de strings con los mismos valores $endpos$. Y si denotamos por $w$ el más largo de estos strings, entonces todos los demás strings son sufijos de $w$.

También sabemos que los primeros sufijos de un string $w$ (si consideramos sufijos en orden descendente de su longitud) están todos contenidos en esta clase de equivalencia, y todos los demás sufijos (al menos uno más: el sufijo vacío) están en algunas otras clases. Denotamos por $t$ el mayor de esos sufijos, y hacemos un enlace de sufijo hacia él.

En otras palabras, un enlace de sufijo (suffix link) $link(v)$ lleva al estado que corresponde al sufijo más largo de $w$ que está en otra clase de $endpos$-equivalencia.

Aquí asumimos que el estado inicial $t_0$ corresponde a su propia clase de equivalencia (que contiene solo el string vacío), y por conveniencia ponemos $endpos(t_0) = {-1, 0, \dots, length(s)-1}$.

Lema 4: Los enlaces de sufijo forman un árbol con raíz $t_0$.

Demostración: Consideremos un estado arbitrario $v \ne t_0$. Un enlace de sufijo $link(v)$ lleva a un estado que corresponde a strings con longitud estrictamente menor (esto se sigue de la definición de los enlaces de sufijo y del Lema 3). Por lo tanto, al movernos a lo largo de los enlaces de sufijo, tarde o temprano llegaremos al estado inicial $t_0$, que corresponde al string vacío.

Lema 5: Si construimos un árbol usando los conjuntos $endpos$ (por la regla de que el conjunto de un nodo padre contiene los conjuntos de todos los hijos como subconjuntos), entonces la estructura coincidirá con el árbol de enlaces de sufijo.

Demostración: El hecho de que podemos construir un árbol usando los conjuntos $endpos$ se sigue directamente del Lema 2 (que cualesquiera dos conjuntos o bien no se intersectan o uno está contenido en el otro).

Consideremos ahora un estado arbitrario $v \ne t_0$, y su enlace de sufijo $link(v)$. De la definición del enlace de sufijo y del Lema 2 se sigue que

$$endpos(v) \subseteq endpos(link(v)),$$

lo que junto con el lema anterior demuestra la afirmación: el árbol de enlaces de sufijo es esencialmente un árbol de conjuntos $endpos$.

Aquí hay un ejemplo de un árbol de enlaces de sufijo en el autómata de sufijos construido para el string $\text{“abcbc”}$. Los nodos están etiquetados con la subcadena más larga de la clase de equivalencia correspondiente.

Recapitulación

Antes de proceder al algoritmo en sí, recapitulamos el conocimiento acumulado e introducimos unas notaciones auxiliares.

• Las subcadenas del string $s$ se pueden descomponer en clases de equivalencia según sus posiciones finales $endpos$.
• El autómata de sufijos consiste del estado inicial $t_0$, así como de un estado por cada clase de $endpos$-equivalencia.
• Para cada estado $v$ coinciden una o varias subcadenas. Denotamos por $longest(v)$ el string más largo de ese tipo, y por $len(v)$ su longitud. Denotamos por $shortest(v)$ la subcadena más corta de ese tipo, y su longitud con $minlen(v)$. Entonces todos los strings correspondientes a este estado son sufijos distintos del string $longest(v)$ y tienen todas las longitudes posibles en el intervalo $[minlen(v); len(v)]$.
• Para cada estado $v \ne t_0$ se define un enlace de sufijo como un enlace que lleva a un estado que corresponde al sufijo del string $longest(v)$ de longitud $minlen(v) - 1$. Los enlaces de sufijo forman un árbol con raíz en $t_0$, y al mismo tiempo este árbol forma una relación de inclusión entre los conjuntos $endpos$.
• Podemos expresar $minlen(v)$ para $v \ne t_0$ usando el enlace de sufijo $link(v)$ como:

$$minlen(v) = len(link(v)) + 1$$

• Si empezamos desde un estado arbitrario $v_0$ y seguimos los enlaces de sufijo, entonces tarde o temprano llegaremos al estado inicial $t_0$. En este caso obtenemos una secuencia de intervalos disjuntos $[minlen(v_i); len(v_i)]$, que en unión forma el intervalo continuo $[0; len(v_0)]$.

Algoritmo

Ahora podemos proceder al algoritmo en sí. El algoritmo será online, es decir, agregaremos los caracteres del string uno por uno, y modificaremos el autómata en consecuencia en cada paso.

Para alcanzar consumo de memoria lineal, solo guardaremos los valores $len$, $link$ y una lista de transiciones en cada estado. No etiquetaremos estados terminales (pero más adelante mostraremos cómo disponer estas etiquetas después de construir el autómata de sufijos).

Inicialmente el autómata consiste de un solo estado $t_0$, que será el índice $0$ (los estados restantes recibirán los índices $1, 2, \dots$). Le asignamos $len = 0$ y $link = -1$ por conveniencia ($-1$ será un estado ficticio, inexistente).

Ahora toda la tarea se reduce a implementar el proceso de agregar un carácter $c$ al final del string actual. Describamos este proceso:

• Sea $last$ el estado correspondiente a todo el string antes de agregar el carácter $c$. (Inicialmente ponemos $last = 0$, y cambiaremos $last$ en el último paso del algoritmo en consecuencia.)

• Creamos un estado nuevo $cur$, y le asignamos $len(cur) = len(last) + 1$. El valor $link(cur)$ no se conoce en ese momento.

• Ahora hacemos el siguiente procedimiento: Empezamos en el estado $last$. Mientras no haya una transición por la letra $c$, agregaremos una transición al estado $cur$, y seguiremos el enlace de sufijo. Si en algún punto ya existe una transición por la letra $c$, entonces nos detendremos y denotaremos este estado con $p$.

• Si no encontramos tal estado $p$, entonces llegamos al estado ficticio $-1$, entonces podemos simplemente asignar $link(cur) = 0$ y salir.

• Supongamos ahora que encontramos un estado $p$, desde el cual existe una transición por la letra $c$. Denotaremos el estado al que lleva la transición con $q$.

• Ahora tenemos dos casos. O bien $len(p) + 1 = len(q)$, o no.

• Si $len(p) + 1 = len(q)$, entonces podemos simplemente asignar $link(cur) = q$ y salir.

• En caso contrario es un poco más complicado. Es necesario clonar el estado $q$: creamos un estado nuevo $clone$, copiamos todos los datos de $q$ (enlace de sufijo y transición) excepto el valor $len$. Asignaremos $len(clone) = len(p) + 1$.

  Después de clonar dirigimos el enlace de sufijo de $cur$ a $clone$, y también de $q$ a clone.

  Finalmente necesitamos caminar desde el estado $p$ hacia atrás usando enlaces de sufijo mientras haya una transición por $c$ al estado $q$, y redirigir todas esas al estado $clone$.

• En cualquiera de los tres casos, después de completar el procedimiento, actualizamos el valor $last$ con el estado $cur$.

Si también queremos saber qué estados son terminales y cuáles no, podemos encontrar todos los estados terminales después de construir el autómata de sufijos completo para todo el string $s$. Para ello, tomamos el estado correspondiente a todo el string (guardado en la variable $last$), y seguimos sus enlaces de sufijo hasta que llegamos al estado inicial. Marcaremos todos los estados visitados como terminales. Es fácil entender que al hacer eso marcaremos exactamente los estados correspondientes a todos los sufijos del string $s$, que son exactamente los estados terminales.

En la siguiente sección veremos en detalle cada paso y mostraremos su corrección.

Aquí solo notamos que, como solo creamos uno o dos estados nuevos por cada carácter de $s$, el autómata de sufijos contiene un número lineal de estados.

La linealidad del número de transiciones, y en general la linealidad del tiempo de ejecución del algoritmo es menos clara, y se demostrarán después de que hayamos demostrado la corrección.

Corrección

• Llamaremos a una transición $(p, q)$ continua si $len(p) + 1 = len(q)$. En caso contrario, es decir, cuando $len(p) + 1 < len(q)$, la transición se llamará no continua.

  Como podemos ver de la descripción del algoritmo, las transiciones continuas y no continuas llevarán a distintos casos del algoritmo. Las transiciones continuas están fijas, y nunca cambiarán otra vez. En contraste, una transición no continua puede cambiar cuando se agregan letras nuevas al string (el extremo de la arista de transición puede cambiar).

• Para evitar ambigüedad denotaremos el string para el cual se construyó el autómata de sufijos antes de agregar el carácter actual $c$ con $s$.

• El algoritmo empieza creando un estado nuevo $cur$, que corresponderá a todo el string $s + c$. Está claro por qué tenemos que crear un estado nuevo. Junto con el carácter nuevo se crea una clase de equivalencia nueva.

• Después de crear un estado nuevo recorremos por enlaces de sufijo empezando desde el estado correspondiente a todo el string $s$. Para cada estado intentamos agregar una transición con el carácter $c$ al estado nuevo $cur$. Así agregamos a cada sufijo de $s$ el carácter $c$. Sin embargo solo podemos agregar estas transiciones nuevas si no entran en conflicto con una ya existente. Por lo tanto, en cuanto encontramos una transición ya existente con $c$ tenemos que detenernos.

• En el caso más simple llegamos al estado ficticio $-1$. Esto significa que agregamos la transición con $c$ a todos los sufijos de $s$. Esto también significa que el carácter $c$ no había formado parte del string $s$ antes. Por lo tanto el enlace de sufijo de $cur$ tiene que llevar al estado $0$.

• En el segundo caso nos encontramos con una transición existente $(p, q)$. Esto significa que intentamos agregar un string $x + c$ (donde $x$ es un sufijo de $s$) a la máquina que ya existe en la máquina (el string $x + c$ ya aparece como subcadena de $s$). Como asumimos que el autómata para el string $s$ está construido correctamente, no deberíamos agregar una transición nueva aquí.

  Sin embargo hay una dificultad. ¿A qué estado debería llevar el enlace de sufijo del estado $cur$? Tenemos que hacer un enlace de sufijo a un estado en el que el string más largo es exactamente $x + c$, es decir, el $len$ de este estado debería ser $len(p) + 1$. Sin embargo es posible que tal estado aún no exista, es decir, $len(q) > len(p) + 1$. En este caso tenemos que crear tal estado, partiendo el estado $q$.

• Si la transición $(p, q)$ resulta ser continua, entonces $len(q) = len(p) + 1$. En este caso todo es simple. Dirigimos el enlace de sufijo de $cur$ al estado $q$.

• En caso contrario la transición es no continua, es decir, $len(q) > len(p) + 1$. Esto significa que el estado $q$ corresponde no solo al sufijo de $s + c$ con longitud $len(p) + 1$, sino también a subcadenas más largas de $s$. No podemos hacer otra cosa que partir el estado $q$ en dos subestados, de modo que el primero tenga longitud $len(p) + 1$.

  ¿Cómo podemos partir un estado? Clonamos el estado $q$, lo que nos da el estado $clone$, y ponemos $len(clone) = len(p) + 1$. Copiamos todas las transiciones de $q$ a $clone$, porque no queremos cambiar los caminos que recorren $q$. También ponemos el enlace de sufijo de $clone$ al destino del enlace de sufijo de $q$, y ponemos el enlace de sufijo de $q$ a $clone$.

  Y después de partir el estado, ponemos el enlace de sufijo de $cur$ a $clone$.

  En el último paso cambiamos algunas de las transiciones a $q$, las redirigimos a $clone$. ¿Qué transiciones tenemos que cambiar? Basta con redirigir solo las transiciones correspondientes a todos los sufijos del string $w + c$ (donde $w$ es el string más largo de $p$), es decir, necesitamos continuar moviéndonos a lo largo de los enlaces de sufijo, empezando desde el vértice $p$ hasta que llegamos al estado ficticio $-1$ o a una transición que lleva a un estado distinto de $q$.

Número lineal de operaciones

Primero hacemos inmediatamente la hipótesis de que el tamaño del alfabeto es constante. Si no es el caso, entonces no será posible hablar de la complejidad temporal lineal. La lista de transiciones desde un vértice se guardará en un árbol balanceado, que permite realizar rápido operaciones de búsqueda de clave y agregar claves. Por lo tanto, si denotamos con $k$ el tamaño del alfabeto, entonces el comportamiento asintótico del algoritmo será $O(n \log k)$ con memoria $O(n)$. Sin embargo, si el alfabeto es lo bastante pequeño, entonces se puede sacrificar memoria evitando árboles balanceados, y guardar las transiciones en cada vértice como un arreglo de longitud $k$ (para búsqueda rápida por clave) y una lista dinámica (para recorrer rápido todas las claves disponibles). Así alcanzamos la complejidad temporal $O(n)$ para el algoritmo, pero a costa de complejidad de memoria $O(n k)$.

Así que consideraremos el tamaño del alfabeto constante, es decir, cada operación de buscar una transición por un carácter, agregar una transición, buscar la siguiente transición — todas estas operaciones se pueden hacer en $O(1)$.

Si consideramos todas las partes del algoritmo, entonces contiene tres lugares en el algoritmo en los que la complejidad lineal no es obvia:

• El primer lugar es el recorrido a través de los enlaces de sufijo desde el estado $last$, agregando transiciones con el carácter $c$.
• El segundo lugar es la copia de transiciones cuando el estado $q$ se clona en un estado nuevo $clone$.
• El tercer lugar es cambiar la transición que lleva a $q$, redirigiéndolas a $clone$.

Usamos el hecho de que el tamaño del autómata de sufijos (tanto en el número de estados como en el número de transiciones) es lineal. (La demostración de la linealidad del número de estados es el algoritmo mismo, y la demostración de linealidad del número de estados se da abajo, después de la implementación del algoritmo).

Así, la complejidad total del primer y segundo lugar es obvia, después de todo cada operación agrega solo una transición nueva amortizada al autómata.

Resta estimar la complejidad total del tercer lugar, en el que redirigimos transiciones que originalmente apuntaban a $q$, a $clone$. Denotamos $v = longest(p)$. Este es un sufijo del string $s$, y con cada iteración su longitud disminuye — y por tanto la posición $v$ como sufijo del string $s$ aumenta de forma monótona con cada iteración. En este caso, si antes de la primera iteración del bucle, el string correspondiente $v$ estaba a profundidad $k$ ($k \ge 2$) de $last$ (contando la profundidad como el número de enlaces de sufijo), entonces después de la última iteración el string $v + c$ será un 2-ésimo enlace de sufijo en el camino desde $cur$ (que se convertirá en el valor nuevo $last$).

Así, cada iteración de este bucle lleva al hecho de que la posición del string $longest(link(link(last))$ como sufijo del string actual aumentará de forma monótona. Por lo tanto este ciclo no puede ejecutarse más de $n$ iteraciones, que era lo que se requería demostrar.

Implementación

Primero describimos una estructura de datos que guardará toda la información sobre una transición específica ($len$, $link$ y la lista de transiciones). Si es necesario se puede agregar un flag terminal aquí, así como otra información. Guardaremos la lista de transiciones en forma de un $map$, que nos permite alcanzar memoria total $O(n)$ y tiempo $O(n \log k)$ para procesar todo el string.

struct state {
    int len, link;
    map<char, int> next;
};

El autómata de sufijos mismo se guardará en un arreglo de estas estructuras $state$. Guardamos el tamaño actual $sz$ y también la variable $last$, el estado correspondiente a todo el string en el momento.

const int MAXLEN = 100000;
state st[MAXLEN * 2];
int sz, last;

Damos una función que inicializa un autómata de sufijos (creando un autómata de sufijos con un solo estado).

void sa_init() {
    st[0].len = 0;
    st[0].link = -1;
    sz++;
    last = 0;
}

Y finalmente damos la implementación de la función principal — que agrega el siguiente carácter al final de la línea actual, reconstruyendo la máquina en consecuencia.

void sa_extend(char c) {
    int cur = sz++;
    st[cur].len = st[last].len + 1;
    int p = last;
    while (p != -1 && !st[p].next.count(c)) {
        st[p].next[c] = cur;
        p = st[p].link;
    }
    if (p == -1) {
        st[cur].link = 0;
    } else {
        int q = st[p].next[c];
        if (st[p].len + 1 == st[q].len) {
            st[cur].link = q;
        } else {
            int clone = sz++;
            st[clone].len = st[p].len + 1;
            st[clone].next = st[q].next;
            st[clone].link = st[q].link;
            while (p != -1 && st[p].next[c] == q) {
                st[p].next[c] = clone;
                p = st[p].link;
            }
            st[q].link = st[cur].link = clone;
        }
    }
    last = cur;
}

Como se mencionó arriba, si se sacrifica memoria ($O(n k)$, donde $k$ es el tamaño del alfabeto), entonces se puede alcanzar el tiempo de construcción de la máquina en $O(n)$, incluso para cualquier tamaño de alfabeto $k$. Pero para esto habrá que guardar un arreglo de tamaño $k$ en cada estado (para saltar rápido a la transición de la letra), y adicionalmente una lista de todas las transiciones (para iterar rápido sobre las transiciones).

Propiedades adicionales

Número de estados

El número de estados en un autómata de sufijos del string $s$ de longitud $n$ no excede $2n - 1$ (para $n \ge 2$).

La demostración es el algoritmo de construcción mismo, ya que inicialmente el autómata consiste de un estado, y en la primera y segunda iteración solo se creará un solo estado, y en los $n-2$ pasos restantes se crearán a lo sumo $2$ estados cada uno.

Sin embargo también podemos mostrar esta estimación sin conocer el algoritmo. Recordemos que el número de estados es igual al número de conjuntos $endpos$ distintos. Además estos conjuntos $endpos$ forman un árbol (un vértice padre contiene todos los conjuntos hijos en su conjunto). Consideremos este árbol y transformémoslo un poco: mientras tenga un vértice interno con solo un hijo (lo que significa que el conjunto del hijo omite al menos una posición del conjunto padre), creamos un hijo nuevo con el conjunto de las posiciones faltantes. Al final tenemos un árbol en el que cada vértice interno tiene grado mayor que uno, y el número de hojas no excede $n$. Por lo tanto no hay más de $2n - 1$ vértices en tal árbol.

Esta cota del número de estados se puede de hecho alcanzar para cada $n$. Un string posible es:

$$\text{“abbb}\dots \text{bbb”}$$

En cada iteración, empezando en la tercera, el algoritmo partirá un estado, resultando en exactamente $2n - 1$ estados.

Número de transiciones

El número de transiciones en un autómata de sufijos de un string $s$ de longitud $n$ no excede $3n - 4$ (para $n \ge 3$).

Demostremos esto:

Primero estimemos el número de transiciones continuas. Consideremos un árbol de expansión de los caminos más largos en el autómata empezando en el estado $t_0$. Este esqueleto consistirá solo de las aristas continuas, y por tanto su número es menor que el número de estados, es decir, no excede $2n - 2$.

Ahora estimemos el número de transiciones no continuas. Sea la transición no continua actual $(p, q)$ con el carácter $c$. Tomamos el string correspondiente $u + c + w$, donde el string $u$ corresponde al camino más largo del estado inicial a $p$, y $w$ al camino más largo de $q$ a cualquier estado terminal. Por un lado, cada tal string $u + c + w$ para cada string incompleto será distinto (ya que los strings $u$ y $w$ se forman solo por transiciones completas). Por otro lado cada tal string $u + c + w$, por la definición de los estados terminales, será un sufijo de todo el string $s$. Como hay solo $n$ sufijos no vacíos de $s$, y ninguno de los strings $u + c + w$ puede contener $s$ (porque todo el string solo contiene transiciones completas), el número total de transiciones incompletas no excede $n - 1$.

Combinando estas dos estimaciones nos da la cota $3n - 3$. Sin embargo, como el número máximo de estados solo se puede alcanzar con el caso de prueba $\text{“abbb\dots bbb”}$ y este caso claramente tiene menos de $3n - 3$ transiciones, obtenemos la cota más ajustada de $3n - 4$ para el número de transiciones en un autómata de sufijos.

Esta cota también se puede alcanzar con el string:

$$\text{“abbb}\dots \text{bbbc”}$$

Aplicaciones

Aquí vemos algunas tareas que se pueden resolver usando el autómata de sufijos. Por simplicidad asumimos que el tamaño del alfabeto $k$ es constante, lo que nos permite considerar la complejidad de agregar un carácter y el recorrido como constantes.

Comprobar ocurrencia

Dado un texto $T$, y varios patrones $P$. Tenemos que comprobar si los strings $P$ aparecen o no como subcadena de $T$.

Construimos un autómata de sufijos del texto $T$ en tiempo $O(length(T))$. Para comprobar si un patrón $P$ aparece en $T$, seguimos las transiciones, empezando desde $t_0$, según los caracteres de $P$. Si en algún punto no existe una transición, entonces el patrón $P$ no aparece como subcadena de $T$. Si podemos procesar todo el string $P$ de esta forma, entonces el string aparece en $T$.

Es claro que esto tomará tiempo $O(length(P))$ por cada string $P$. Además el algoritmo de hecho encuentra la longitud del prefijo más largo de $P$ que aparece en el texto.

Número de subcadenas distintas

Dado un string $S$. Se quiere calcular el número de subcadenas distintas.

Construyamos un autómata de sufijos para el string $S$.

Cada subcadena de $S$ corresponde a algún camino en el autómata. Por lo tanto el número de subcadenas distintas es igual al número de caminos distintos en el autómata empezando en $t_0$.

Dado que el autómata de sufijos es un grafo dirigido acíclico, el número de formas distintas se puede calcular usando programación dinámica.

A saber, sea $d[v]$ el número de formas, empezando en el estado $v$ (incluyendo el camino de longitud cero). Entonces tenemos la recursión:

$$d[v] = 1 + \sum_{w : (v, w, c) \in DAWG} d[w]$$

Es decir, $d[v]$ se puede expresar como la suma de respuestas para todos los extremos de las transiciones de $v$.

El número de subcadenas distintas es el valor $d[t_0] - 1$ (ya que no contamos la subcadena vacía).

Complejidad temporal total: $O(length(S))$

Como alternativa, podemos aprovechar el hecho de que cada estado $v$ coincide con subcadenas de longitud $[minlen(v),len(v)]$. Por lo tanto, dado $minlen(v) = 1 + len(link(v))$, tenemos el total de subcadenas distintas en el estado $v$ siendo $len(v) - minlen(v) + 1 = len(v) - (1 + len(link(v))) + 1 = len(v) - len(link(v))$.

Esto se demuestra de forma sucinta abajo:

long long get_diff_strings(){
    long long tot = 0;
    for(int i = 1; i < sz; i++) {
        tot += st[i].len - st[st[i].link].len;
    }
    return tot;
}

Aunque esto también es $O(length(S))$, no requiere espacio extra ni llamadas recursivas, en consecuencia corre más rápido en la práctica.

Longitud total de todas las subcadenas distintas

Dado un string $S$. Queremos calcular la longitud total de todas sus subcadenas distintas.

La solución es similar a la anterior, solo que ahora es necesario considerar dos cantidades para la parte de programación dinámica: el número de subcadenas distintas $d[v]$ y su longitud total $ans[v]$.

Ya describimos cómo calcular $d[v]$ en la tarea anterior. El valor $ans[v]$ se puede calcular usando la recursión:

$$ans[v] = \sum_{w : (v, w, c) \in DAWG} d[w] + ans[w]$$

Tomamos la respuesta de cada vértice adyacente $w$, y le sumamos $d[w]$ (ya que cada subcadena es un carácter más larga cuando se empieza desde el estado $v$).

Otra vez esta tarea se puede calcular en tiempo $O(length(S))$.

Como alternativa, podemos, otra vez, aprovechar el hecho de que cada estado $v$ coincide con subcadenas de longitud $[minlen(v),len(v)]$. Como $minlen(v) = 1 + len(link(v))$ y la fórmula de la serie aritmética $S_n = n \cdot \frac{a_1+a_n}{2}$ (donde $S_n$ denota la suma de $n$ términos, $a_1$ representando el primer término, y $a_n$ representando el último), podemos calcular la longitud de las subcadenas en un estado en tiempo constante. Luego sumamos estos totales para cada estado $v \neq t_0$ en el autómata. Esto se muestra en el código de abajo:

long long get_tot_len_diff_substings() {
    long long tot = 0;
    for(int i = 1; i < sz; i++) {
        long long shortest = st[st[i].link].len + 1;
        long long longest = st[i].len;
        
        long long num_strings = longest - shortest + 1;
        long long cur = num_strings * (longest + shortest) / 2;
        tot += cur;
    }
    return tot;
}

Este enfoque corre en tiempo $O(length(S))$, pero experimentalmente corre 20x más rápido que la versión de programación dinámica con memoización en strings aleatorizados. No requiere espacio extra ni recursión.

$k$-ésima subcadena lexicográfica {data-toc-label=“k-ésima subcadena lexicográfica”}

Dado un string $S$. Tenemos que responder múltiples consultas. Para cada número dado $K_i$ tenemos que encontrar el $K_i$-ésimo string en la lista ordenada lexicográficamente de todas las subcadenas.

La solución a este problema se basa en la idea de los dos problemas anteriores. La $k$-ésima subcadena lexicográfica corresponde al $k$-ésimo camino lexicográfico en el autómata de sufijos. Por lo tanto, después de contar el número de caminos desde cada estado, podemos buscar fácilmente el $k$-ésimo camino empezando desde la raíz del autómata.

Esto toma tiempo $O(length(S))$ para el preprocesamiento y luego $O(length(ans) \cdot k)$ por cada consulta (donde $ans$ es la respuesta a la consulta y $k$ es el tamaño del alfabeto).

Menor desplazamiento cíclico

Dado un string $S$. Queremos encontrar el desplazamiento cíclico lexicográficamente más pequeño.

Construimos un autómata de sufijos para el string $S + S$. Entonces el autómata contendrá en sí mismo como caminos todos los desplazamientos cíclicos del string $S$.

En consecuencia el problema se reduce a encontrar el camino lexicográficamente más pequeño de longitud $length(S)$, lo que se puede hacer de forma trivial: empezamos en el estado inicial y pasamos de forma voraz por las transiciones con el carácter mínimo.

La complejidad temporal total es $O(length(S))$.

Número de ocurrencias

Para un texto dado $T$. Tenemos que responder múltiples consultas. Para cada patrón dado $P$ tenemos que averiguar cuántas veces aparece el string $P$ en el string $T$ como subcadena.

Construimos el autómata de sufijos para el texto $T$.

Luego hacemos el siguiente preprocesamiento: para cada estado $v$ en el autómata calculamos el número $cnt[v]$ que es igual al tamaño del conjunto $endpos(v)$. De hecho todos los strings correspondientes al mismo estado $v$ aparecen en el texto $T$ una cantidad igual de veces, que es igual al número de posiciones en el conjunto $endpos$.

Sin embargo no podemos construir los conjuntos $endpos$ de forma explícita, por lo tanto solo consideramos sus tamaños $cnt$.

Para calcularlos procedemos de la siguiente forma. Para cada estado, si no fue creado por clonación (y si no es el estado inicial $t_0$), lo inicializamos con $cnt = 1$. Luego recorreremos todos los estados en orden decreciente de su longitud $len$, y sumaremos el valor actual $cnt[v]$ a los enlaces de sufijo:

$$cnt[link(v)] \text{ += } cnt[v]$$

Esto da el valor correcto para cada estado.

¿Por qué es correcto? El número total de estados obtenidos no vía clonación es exactamente $length(T)$, y los primeros $i$ de ellos aparecieron cuando agregamos los primeros $i$ caracteres. En consecuencia para cada uno de estos estados contamos la posición correspondiente en la que se procesó. Por lo tanto inicialmente tenemos $cnt = 1$ para cada estado de ese tipo, y $cnt = 0$ para todos los demás.

Luego aplicamos la siguiente operación para cada $v$: $cnt[link(v)] \text{ += } cnt[v]$. El significado detrás de esto es que si un string $v$ aparece $cnt[v]$ veces, entonces también todos sus sufijos aparecen en las mismas posiciones finales exactas, por tanto también $cnt[v]$ veces.

¿Por qué no sobrecontamos en este procedimiento (es decir, no contamos algunas posiciones dos veces)? Porque agregamos las posiciones de un estado a solo un otro estado, así que no puede ocurrir que un estado dirija sus posiciones a otro estado dos veces de dos formas distintas.

Así podemos calcular las cantidades $cnt$ para todos los estados del autómata en tiempo $O(length(T))$.

Después de eso responder una consulta es simplemente consultar el valor $cnt[t]$, donde $t$ es el estado correspondiente al patrón, si tal estado existe. En caso contrario responder con $0$. Responder una consulta toma tiempo $O(length(P))$.

Posición de la primera ocurrencia

Dado un texto $T$ y múltiples consultas. Para cada string de consulta $P$ queremos encontrar la posición de la primera ocurrencia de $P$ en el string $T$ (la posición del inicio de $P$).

Otra vez construimos un autómata de sufijos. Además precomputamos la posición $firstpos$ para todos los estados del autómata, es decir, para cada estado $v$ queremos encontrar la posición $firstpos[v]$ del final de la primera ocurrencia. En otras palabras, queremos encontrar de antemano el elemento mínimo de cada conjunto $endpos$ (ya que obviamente no podemos mantener todos los conjuntos $endpos$ de forma explícita).

Para mantener estas posiciones $firstpos$ extendemos la función sa_extend(). Cuando creamos un estado nuevo $cur$, ponemos:

$$firstpos(cur) = len(cur) - 1$$

Y cuando clonamos un vértice $q$ como $clone$, ponemos:

$$firstpos(clone) = firstpos(q)$$

(ya que la única otra opción para un valor sería $firstpos(cur)$ que es definitivamente demasiado grande)

Así la respuesta a una consulta es simplemente $firstpos(t) - length(P) + 1$, donde $t$ es el estado correspondiente al string $P$. Responder una consulta otra vez toma solo tiempo $O(length(P))$.

Todas las posiciones de ocurrencia

Esta vez tenemos que mostrar todas las posiciones de las ocurrencias en el string $T$.

Otra vez construimos un autómata de sufijos para el texto $T$. Similar a la tarea anterior computamos la posición $firstpos$ para todos los estados.

Claramente $firstpos(t)$ es parte de la respuesta, si $t$ es el estado correspondiente a un string de consulta $P$. Así tomamos en cuenta el estado del autómata que contiene $P$. ¿Qué otros estados necesitamos tomar en cuenta? Todos los estados que corresponden a strings para los cuales $P$ es un sufijo. En otras palabras necesitamos encontrar todos los estados que pueden alcanzar el estado $t$ vía enlaces de sufijo.

Por lo tanto para resolver el problema necesitamos guardar para cada estado una lista de referencias de sufijo que llevan a él. La respuesta a la consulta entonces contendrá todos los $firstpos$ para cada estado que podemos encontrar en un DFS / BFS empezando desde el estado $t$ usando solo las referencias de sufijo.

En general, esto requiere $O(length (T))$ para el preprocesamiento y $O(length(P) + answer(P))$ por cada petición, donde $answer(P)$ — este es el tamaño de la respuesta.

Primero, bajamos por el autómata por cada carácter del patrón para encontrar nuestro nodo de inicio requiriendo $O(length(P))$. Luego, usamos nuestro workaround que funcionará en tiempo $O(answer(P))$, porque no visitaremos un estado dos veces (porque solo un enlace de sufijo sale de cada estado, así que no puede haber dos caminos distintos que lleven al mismo estado).

Solo debemos tener en cuenta que dos estados distintos pueden tener el mismo valor $firstpos$. Esto ocurre si un estado se obtuvo clonando otro. Sin embargo, esto no arruina la complejidad, ya que cada estado solo puede tener a lo sumo un clon.

Además, también podemos deshacernos de las posiciones duplicadas, si no emitimos las posiciones de los estados clonados. De hecho un estado, al que un estado clonado puede llegar, también es alcanzable desde el estado original. Así si recordamos el flag is_cloned para cada estado, podemos simplemente ignorar los estados clonados y solo emitir $firstpos$ para todos los demás estados.

Aquí hay algunos esbozos de implementación:

struct state {
    ...
    bool is_clone;
    int first_pos;
    vector<int> inv_link;
};
 
// after constructing the automaton
for (int v = 1; v < sz; v++) {
    st[st[v].link].inv_link.push_back(v);
}
 
// output all positions of occurrences
void output_all_occurrences(int v, int P_length) {
    if (!st[v].is_clone)
        cout << st[v].first_pos - P_length + 1 << endl;
    for (int u : st[v].inv_link)
        output_all_occurrences(u, P_length);
}

String más corto que no aparece

Dado un string $S$ y un cierto alfabeto. Tenemos que encontrar un string de la menor longitud, que no aparece en $S$.

Aplicaremos programación dinámica sobre el autómata de sufijos construido para el string $S$.

Sea $d[v]$ la respuesta para el nodo $v$, es decir, ya procesamos parte de la subcadena, estamos actualmente en el estado $v$, y queremos encontrar el menor número de caracteres que hay que agregar para encontrar una transición inexistente. Calcular $d[v]$ es muy simple. Si no hay transición usando al menos un carácter del alfabeto, entonces $d[v] = 1$. En caso contrario un carácter no es suficiente, y así necesitamos tomar el mínimo de todas las respuestas de todas las transiciones:

$$d[v] = 1 + \min_{w:(v,w,c) \in SA} d[w].$$

La respuesta al problema será $d[t_0]$, y el string real se puede restaurar usando el arreglo calculado $d[]$.

Subcadena común más larga de dos strings

Dados dos strings $S$ y $T$. Tenemos que encontrar la subcadena común más larga, es decir, un string $X$ que aparece como subcadena en $S$ y también en $T$.

Construimos un autómata de sufijos para el string $S$.

Ahora tomaremos el string $T$, y para cada prefijo buscaremos el sufijo más largo de este prefijo en $S$. En otras palabras, para cada posición en el string $T$, queremos encontrar la subcadena común más larga de $S$ y $T$ que termina en esa posición.

Para ello usaremos dos variables, el estado actual $v$, y la longitud actual $l$. Estas dos variables describirán la parte coincidente actual: su longitud y el estado que le corresponde.

Inicialmente $v = t_0$ y $l = 0$, es decir, la coincidencia está vacía.

Ahora describamos cómo podemos agregar un carácter $T[i]$ y recalcular la respuesta para él.

• Si hay una transición desde $v$ con el carácter $T[i]$, entonces simplemente seguimos la transición y aumentamos $l$ en uno.
• Si no hay tal transición, tenemos que acortar la parte coincidente actual, lo que significa que necesitamos seguir el enlace de sufijo: $v = link(v)$. Al mismo tiempo, la longitud actual tiene que acortarse. Obviamente necesitamos asignar $l = len(v)$, ya que después de pasar por el enlace de sufijo terminamos en un estado cuyo string más largo correspondiente es una subcadena.
• Si todavía no hay transición usando el carácter requerido, repetimos y otra vez vamos por el enlace de sufijo y disminuimos $l$, hasta que encontramos una transición o llegamos al estado ficticio $-1$ (lo que significa que el símbolo $T[i]$ no aparece en absoluto en $S$, así que asignamos $v = l = 0$).

La respuesta a la tarea será el máximo de todos los valores $l$.

La complejidad de esta parte es $O(length(T))$, ya que en un movimiento podemos o bien aumentar $l$ en uno, o hacer varios pases a través de los enlaces de sufijo, cada uno termina reduciendo el valor $l$.

Implementación:

string lcs (string S, string T) {
    sa_init();
    for (int i = 0; i < S.size(); i++)
        sa_extend(S[i]);
 
    int v = 0, l = 0, best = 0, bestpos = 0;
    for (int i = 0; i < T.size(); i++) {
        while (v && !st[v].next.count(T[i])) {
            v = st[v].link ;
            l = st[v].len;
        }
        if (st[v].next.count(T[i])) {
            v = st [v].next[T[i]];
            l++;
        }
        if (l > best) {
            best = l;
            bestpos = i;
        }
    }
    return T.substr(bestpos - best + 1, best);
} 

Subcadena común más larga de múltiples strings

Hay $k$ strings $S_i$ dados. Tenemos que encontrar la subcadena común más larga, es decir, un string $X$ que aparece como subcadena en cada string $S_i$.

Unimos todos los strings en un string grande $T$, separando los strings por caracteres especiales $D_i$ (uno por cada string):

$$T = S_1 + D_1 + S_2 + D_2 + \dots + S_k + D_k.$$

Luego construimos el autómata de sufijos para el string $T$.

Ahora necesitamos encontrar un string en la máquina, que está contenido en todos los strings $S_i$, y esto se puede hacer usando los caracteres especiales agregados. Nótese que si una subcadena está incluida en algún string $S_j$, entonces en el autómata de sufijos existe un camino empezando desde esta subcadena que contiene el carácter $D_j$ y no contiene los otros caracteres $D_1, \dots, D_{j-1}, D_{j+1}, \dots, D_k$.

Así necesitamos calcular la alcanzabilidad, que nos dice para cada estado de la máquina y cada símbolo $D_i$ si existe tal camino. Esto se puede computar fácilmente con DFS o BFS y programación dinámica. Después de eso, la respuesta al problema será el string $longest(v)$ para el estado $v$, desde el cual existían los caminos para todos los caracteres especiales.

Problemas de práctica

• CSES - Finding Patterns 
• CSES - Counting Patterns 
• CSES - String Matching 
• CSES - Patterns Positions 
• CSES - Distinct Substrings 
• CSES - Word Combinations 
• CSES - String Distribution 
• AtCoder - K-th Substring 
• SPOJ - SUBLEX 
• Codeforces - Cyclical Quest 
• Codeforces - String