Automatón de Aho-Corasick

El problema fundamental que aborda el Autómata de Aho-Corasick (AC) es la coincidencia de múltiples cadenas.

La idea central consiste en construir una estructura Trie con todas las cadenas de patrones y luego incorporar la lógica de los punteros de fallo del algoritmo KMP.

Definamos num[u][i] como el estado al que se transita desde el estado u (que representa un prefijo de cadena) al añadir el carácter i. fail[u] representa el estado que se puede alcanzar al encontrar el sufijo más largo de la cadena representada por u, de manera análoga al puntero fail en KMP.

Construcción

La construcción se realiza nivel por nivel. Suponiendo que los nodos hasta la profundidad u-1 ya han sido procesados, consideramos el nodo u.

Para las transiciones exisetntes en el Trie desde u (num[u][i]), actualizamos estas transiciones y, consecuentemente, los punteros de fallo fail[num[u][i]]. Para las transiciones no existentes, se heredan del puntero de fallo del estado actual: num[u][j] = num[fail[u]][j].

A continuación, se presenta un fragmento de código para la construcción:

void construirAC() {
   colaHead = 0;
   colaTail = -1;
   for (int i = 0; i < 26; ++i) {
       if (transicion[0][i]) {
           grafo[0].push_back(transicion[0][i]);
           cola[++colaTail] = transicion[0][i];
       }
   }
   while (colaHead <= colaTail) {
       int estadoActual = cola[colaHead++];
       for (int i = 0; i < 26; ++i) {
           if (transicion[estadoActual][i]) {
               fallo[transicion[estadoActual][i]] = transicion[fallo[estadoActual]][i];
               cola[++colaTail] = transicion[estadoActual][i];
               grafo[fallo[transicion[estadoActual][i]]].push_back(transicion[estadoActual][i]);
           } else {
               transicion[estadoActual][i] = transicion[fallo[estadoActual]][i];
           }
       }
   }
}
   

Resolución de Problemas

Para la coincidencia de múltiples cadenas, se recorre el autómata siguiendo las transiciones num[u][i] y se marcan los estados visitados. Es importante notar que si un estado u es alcanzado, entonces todos los estados en la cadena de fallos (fail[u], fail[fail[u]], etc.) también deben ser considerados como alcanzados. Por lo tanto, se marca el estado u y, al final, se propaga esta marca a lo largo de la estructura de fallos.

Arreglo de Sufijos (Suffix Array)

El problema fundamental del Arreglo de Sufijos (SA) es determinar el orden lexicográfico de todos los sufijos de una cadena dada S de longitud n. Específicamente, se busca el rango de cada sufijo que comienza en la posición i.

Soluciones

1. Ordenamiento + Búsqueda Binaria + Hash

Comparar dos sufijos T_i y T_j es relativamente sencillo. Utilizando búsqueda binaria y hash, se puede calcular la Longitud del Prefijo Común Más Largo (LCP) entre ellos. Luego, se compara el siguiente carácter para determinar el orden lexicográfico. Con esta capacidad de comparación, se pueden ordenar todos los sufijos utilizando un algoritmo de ordenamiento estándar (como sort).

La complejidad temporal es O(n * log^2 n), lo cual es considerablemente lento y tiene una gran constante.

2. Aumento por Duplicación + Ordenamiento Radix

Este enfoque se basa en la premisa de que si se conocen los rangos de todos los subcadenas de longitud 2^x, se pueden obtener los rangos de las subcadenas de longitud 2^(x+1) en tiempo O(n).

La lógica es la siguiente: para comparar las subcadenas que comienzan en i y j de longitud 2^(x+1), se divide cada subcadena en dos mitades de longitud 2^x y se comparan por pares. Primero, se compara S[i...i+2^x-1] con S[j...j+2^x-1], y luego S[i+2^x...i+2^(x+1)-1] con S[j+2^x...j+2^(x+1)-1].

Esto se traduce esencialmente en un ordenamiento por claves dobles, que se implementa eficientemente con ordenamiento radix. Primero se agrupa por la primera clave (la primera mitad) y luego se ordena internamente por la segunda clave (la segunda mitad). Este proceso se puede realizar en O(n). Es crucial manejar los duplicados correctamente para evitar problemas.

La complejidad temporal total es O(n * log n). Aunque la constante es menor que el método anterior, una implementación estándar de ordenamiento radix puede ser lenta. Existe una implementación optimizada con una constante muy pequeña.

void ordenarSA() {
   int limite = 128; // Límite para caracteres ASCII
   for (int i = 1; i <= n; ++i) {
       contador[rango[i] = cadena[i]]++;
   }
   for (int i = 1; i <= limite; ++i) {
       contador[i] += contador[i - 1];
   }
   for (int i = 1; i <= n; ++i) {
       arregloSufijos[contador[rango[i]]--] = i;
   }

   for (int p = 1; ; p <<= 1) {
       int puntero = 0;
       // Ordenar por la segunda clave (segmento [i+p...])
       for (int i = n - p + 1; i <= n; ++i) {
           arregloSufijosAux[++puntero] = i;
       }
       for (int i = 1; i <= n; ++i) {
           if (arregloSufijos[i] > p) {
               arregloSufijosAux[++puntero] = arregloSufijos[i] - p;
           }
       }

       // Ordenar por la primera clave (segmento [i...i+p-1])
       memset(contador, 0, sizeof(contador));
       for (int i = 1; i <= n; ++i) {
           contador[rango[i]]++;
       }
       for (int i = 1; i <= limite; ++i) {
           contador[i] += contador[i - 1];
       }
       for (int i = n; i >= 1; --i) {
           arregloSufijos[contador[rango[arregloSufijosAux[i]]]--] = arregloSufijosAux[i];
       }

       memcpy(rangoAux, rango, sizeof(rango));
       limite = 0;
       for (int i = 1; i <= n; ++i) {
           if (rangoAux[arregloSufijos[i]] == rangoAux[arregloSufijos[i - 1]] &&
               rangoAux[arregloSufijos[i] + p] == rangoAux[arregloSufijos[i - 1] + p]) {
               rango[arregloSufijos[i]] = limite;
           } else {
               rango[arregloSufijos[i]] = ++limite;
           }
       }
       if (limite == n) {
           break;
       }
   }
}
   

Esta implementación puede manejar datos de hasta 10^6 eficientemente.

3. O(n)

Aunque existen algoritmos O(n), la versión O(n log n) con implementación optimizada suele ser suficiente para la mayoría de los casos.

Aplicaciones Adicionales

1. Array de Alturas (Height Array)

Se introduce el array height, donde height[i] representa la longitud del LCP entre los sufijos sa[i] y sa[i+1].

Se puede calcular eficientemente en O(n). Se observa que para el sufijo que comienza en la posición i, su height[rank[i]] es al menos height[rank[i-1]] - 1. La prueba es bastante intuitiva.

void calcularAltura() {
   int longitudActual = 0;
   for (int i = 1; i <= n; ++i) {
       if (rango[i] == 1) {
           longitudActual = 0;
           continue;
       }
       if (longitudActual) {
           longitudActual--;
       }
       while (i + longitudActual <= n && 
              arregloSufijos[rango[i] - 1] + longitudActual <= n && 
              cadena[i + longitudActual] == cadena[arregloSufijos[rango[i] - 1] + longitudActual]) {
           longitudActual++;
       }
       altura[rango[i]] = longitudActual;
   }
}
   

2. Calcular LCP de Dos Sufijos Cualesquiera

Esto se reduce a encontrar el mínimo valor en el array height entre los índices correspondientes a los dos sufijos en el arreglo de sufijos ordenado. Formalmente, para los sufijos sa[i] y sa[j] (asumiendo i < j), el LCP es min(height[k]) para k desde i hasta j-1.

La demostración más directa de esto se puede hacer usando un árbol de sufijos. En un árbol de sufijos, la longitud del LCP de dos sufijos es la profundidad del ancestro común más bajo (LCA) de los nodos que representan esos sufijos. La relación entre el array de alturas y el LCA es un resultado clásico.

3. Calcular el Número de Subcadenas Distintas

La contribución de cada sufijo que comienza en la posición i al número total de subcadenas distintas es n - i + 1 - height[i-1]. Esto se debe a que n - i + 1 es la longitud del sufijo, y height[i-1] representa las subcadenas que ya han sido contadas como prefijos de sufijos lexicográficamente anteriores.

Por lo tanto, la respuesta total es sum(n - i + 1) - sum(height[i]), que se simplifica a n*(n+1)/2 - sum(height[i]).

Automatón de Sufijos (SAM)

El Autómata de Sufijos (SAM) es un autómata con propiedades excepcionales. Su construcción, aunque a veces parezca mágica, es eficiente y la demostración de su complejidad temporal puede ser un poco intrincada.

Propiedades

Cada nodo en un SAM representa un conjunto de subcadenas que comparten la misma posición final de aparición (endpos). Las subcadenas dentro de un mismo estado son de longitudes consecutivas. El parámetro len[u] almacena la longitud de la subcadena más larga en el estado u. Todas las subcadenas representadas por un estado son sufijos de la subcadena más larga de ese estado.

Las transiciones (aristas) representan la adición de un carácter y forman un Grafo Dirigido Acíclico (DAG). Cada camino distinto desde el estado inicial del SAM corresponde a una subcadena única de la cadena original.

Los punteros de fallo (fail) conectan un estado con el estado que representa el sufijo más largo de su conjunto de subcadenas, pero que pertenece a un conjunto de endpos diferente.

Construcción

Se emplea un método incremental. Al añadir el carácter S[i] = c:

1. Se crea un nuevo estado np para representar las nuevas subcadenas que terminan en i. Se establece len[np] = i y siz[np] = 1 (inicialmente). 2. Se recorren los punteros de fallo desde el último estado añadido (las) hasta encontrar un estado p que tenga una transición para el carácter c (go[p][id]). Si no existe, se añade la transición go[p][id] = np y se continúa hacia arriba. 3. Si se encuentra una transición go[p][id] que lleva al estado q:

• Si len[q] == len[p] + 1, significa que las endpos de q se actualizan correctamente, así que solo se establece fail[np] = q.
• Si len[q] != len[p] + 1, se debe "dividir" el estado q. Se crea un nuevo estado nq con longitud len[p] + 1, copiando las transiciones y el puntero de fallo de q. Luego, se actualizan las transiciones de p y sus ancestros de fallo para apuntar a nq en lugar de q. Finalmente, se establece fail[np] = fail[q] = nq.

El estado las se actualiza a np.

El número de estados en un SAM nunca excede 2n-1 y el número de transiciones no supera 3n-4.

void construirSAM() {
   scanf("%s", cadenaOriginal + 1); // Asume cadenaOriginal es global
   int n = strlen(cadenaOriginal + 1);
   estadoTotal = ultimoEstado = 1; // Inicializa los estados
   len[estadoTotal] = 0; // Longitud del estado inicial es 0
   siz[estadoTotal] = 0; // Contador de ocurrencias

   for (int i = 1; i <= n; ++i) {
       int idChar = cadenaOriginal[i] - 'a'; // Índice del carácter
       int estadoNuevo = ++estadoTotal;
       len[estadoNuevo] = i; // Longitud del nuevo estado
       siz[estadoNuevo] = 1; // Inicialmente, una ocurrencia

       int estadoPrevio = ultimoEstado;
       // Avanzar por fallos para crear transiciones
       while (estadoPrevio != 0 && !go[estadoPrevio][idChar]) {
           go[estadoPrevio][idChar] = estadoNuevo;
           estadoPrevio = fail[estadoPrevio];
       }

       if (!estadoPrevio) {
           fail[estadoNuevo] = 1; // Fallo apunta al estado inicial
       } else {
           int estadoSiguiente = go[estadoPrevio][idChar];
           if (len[estadoSiguiente] == len[estadoPrevio] + 1) {
               fail[estadoNuevo] = estadoSiguiente; // Caso simple
           } else {
               // Caso de división de estado
               int estadoCopiado = ++estadoTotal;
               len[estadoCopiado] = len[estadoPrevio] + 1;
               memcpy(go[estadoCopiado], go[estadoSiguiente], sizeof(go[estadoSiguiente]));
               fail[estadoCopiado] = fail[estadoSiguiente];
               // Actualizar transiciones que apuntaban al estado original 'q'
               while (estadoPrevio != 0 && go[estadoPrevio][idChar] == estadoSiguiente) {
                   go[estadoPrevio][idChar] = estadoCopiado;
                   estadoPrevio = fail[estadoPrevio];
               }
               fail[estadoNuevo] = fail[estadoSiguiente] = estadoCopiado;
           }
       }
       ultimoEstado = estadoNuevo; // Actualizar el último estado
   }
}
   

Aplicaciones

1. Capacidades del SA

El SAM puede resolver todos los problemas que el SA puede resolver, a menudo con enfoques más directos.

• Número de subcadensa distintas: Es equivalente al número de caminos en el DAG del SAM. Se puede calcular con DP. Alternativamente, la suma de len[u] - len[fail[u]] para todos los estados u da el resultado.
• k-ésima subcadena más pequeña/grande: Tras calcular el número de caminos (subcadenas distintas), se puede usar búsqueda binaria para encontrar la k-ésima subcadena.

2. Construcción de Árbol de Sufijos

Sorprendentemente, el árbol de sufijos se puede construir a partir de un SAM. Si se construye un SAM para la cadena invertida, el grafo formado por los punteros de fallo (fail) es isomorfo al árbol de sufijos de la cadena original.

Con el árbol de sufijos, muchos problemas relacionados con sufijos se vuelven más manejables al tratarse como problemas en un árbol.