Entrevista técnica: ¿cómo implementar un autómata de sufijos y explicar los estados clonados?

Pregunta

Dada una cadena s, construye un autómata de sufijos (SAM) en línea. Implementa extend(c), explica len, link, las transiciones y endpos, y utiliza la estructura para contar subcadenas distintas, contar ocurrencias de patrones o encontrar una subcadena común más larga. Explica por qué el número de estados es O(n) y cuándo se requiere un clon.

Lo que el entrevistador está evaluando

• Si puedes describir un estado como una clase de equivalencia endpos en lugar de un nodo de trie ordinario.
• Si distingues las ramas de enlace directo, enlace a la raíz y clon durante la construcción.
• Si preservas len[link[v]] < len[v], las transiciones deterministas y el invariante del árbol de enlaces de sufijo.
• Si puedes convertir el invariante estructural en resultados de consultas y complejidad.

Respuesta modelo

Un SAM es el DFA parcial mínimo que reconoce cada subcadena de la cadena de origen. El estado v almacena la longitud máxima representada len[v]; link[v] apunta al sufijo más largo en otra clase de equivalencia. El estado representa el intervalo consecutivo (len[link[v]], len[v]], por lo que un estado puede representar varias longitudes de subcadenas.

Cuando se agrega un carácter, crea cur y recorre los enlaces de sufijo, agregando la transición faltante. Si un destino existente q satisface len[p]+1 == len[q], enlaza cur directamente a q. De lo contrario, copia q en un clon con len = len[p]+1, redirige las transiciones relevantes en la ruta de enlaces de sufijo y apunta tanto link[q] como link[cur] al clon. El clon restablece el invariante de longitud consecutiva.

Cada estado que no sea la raíz aporta len[v] - len[link[v]] subcadenas distintas. Para contar ocurrencias, inicializa en uno los estados correspondientes a los prefijos de origen y luego propaga los conteos a los enlaces de sufijo en orden decreciente de len.

Esquema de implementación

El pseudocódigo a continuación muestra la construcción; las transiciones pueden usar un mapa hash o un mapa ordenado.

extend(c):
  cur = new state
  len[cur] = len[last] + 1
  p = last
  while p != -1 and c not in next[p]:
    next[p][c] = cur
    p = link[p]
  if p == -1:
    link[cur] = root
  else:
    q = next[p][c]
    if len[p] + 1 == len[q]:
      link[cur] = q
    else:
      clone = copy(q)
      len[clone] = len[p] + 1
      while p != -1 and next[p][c] == q:
        next[p][c] = clone
        p = link[p]
      link[q] = link[cur] = clone
  last = cur

Suma len[v] - len[link[v]] sobre los estados que no son la raíz para obtener el conteo de subcadenas distintas. Para un conteo de ocurrencias, sigue las transiciones hasta el estado del patrón y lee el conteo propagado en orden decreciente de longitud.

Errores comunes

• Tratar el SAM como un trie que solo acepta sufijos, en lugar de una compresión de todas las clases endpos.
• Copiar las transiciones de un clon pero dejar sus enlaces inconsistentes, lo que rompe los intervalos de longitud posteriores.
• Redirigir muy pocas transiciones porque el recorrido de enlaces de sufijo se detiene antes del primer estado que ya no apunta a q.
• Contar cada clon como una ocurrencia de prefijo de origen, inflando todos los conteos de ocurrencias.
• Usar un arreglo de transiciones fijo para un alfabeto grande sin especificar sus suposiciones de memoria y codificación.

Compensaciones de complejidad

Con un alfabeto fijo o transiciones con hash, la construcción toma O(n) en tiempo y espacio, con a lo sumo aproximadamente 2n-1 estados. Los mapas de transiciones ordenados agregan un factor relacionado con las operaciones del alfabeto. El SAM es muy adecuado para muchas consultas de subcadenas en un texto fijo; los arreglos de sufijos pueden ser más fáciles de controlar para el recorrido lexicográfico, el trabajo con LCP y la localidad de caché.

El límite lineal asume inserciones al final en línea. Insertar o eliminar en el medio, o actualizar ambos extremos, requiere una estructura diferente; extend no se puede reutilizar simplemente manteniendo su invariante.

Comienza con la cadena vacía, un carácter, caracteres repetidos y una entrada que active un clon como abbb. Luego compara cadenas aleatorias contra conjuntos por fuerza bruta para conteos de subcadenas distintas y de ocurrencias. Para la subcadena común más larga, transmite la segunda cadena a través del SAM y sigue los enlaces de sufijo ante discrepancias.

Referencias

• Notas sobre SAM de CP-algorithms: intervalos de estado, construcción de clones y fórmulas de consulta.
• Artículo del autómata de subcadenas más pequeño de Blumer et al.: los límites teóricos de estados y transiciones.
• Notas de algoritmos de cadenas de Carnegie Mellon: cuándo son preferibles los arreglos de sufijos y los autómatas de sufijos.

Preguntas de seguimiento

¿Por qué cada estado representa un intervalo de longitud consecutivo?

Las subcadenas en una clase endpos forman una secuencia de longitudes sin huecos. Los enlaces de sufijo identifican la clase límite que contiene el sufijo propio más largo, por lo que el intervalo es exactamente (len[link[v]], len[v]].

¿Cuándo se requiere un clon?

Si un destino existente q tiene len[q] > len[p]+1, está transportando dos rangos de longitud no consecutivos. Copiar sus transiciones y separar un clon restablece el invariante.

¿Por qué la suma de intervalos cuenta las subcadenas distintas?

Los intervalos de estado son disjuntos, y cada longitud representada corresponde a una subcadena distinta. Por lo tanto, sumar el tamaño de cada intervalo cuenta cada subcadena distinta no vacía exactamente una vez.

¿Cómo deben compararse el SAM y Aho–Corasick?

El SAM indexa todas las subcadenas de un texto y admite estadísticas agregadas. Aho–Corasick indexa un conjunto conocido de patrones para coincidencia por lotes. El hecho de que el texto o el conjunto de patrones sea fijo suele determinar cuál es la mejor construcción.

¿Cómo se encuentra la subcadena común más larga?

Construye un SAM para S, luego escanea T. Sigue las transiciones mientras rastreas la longitud de coincidencia actual; ante una discrepancia, sigue los enlaces de sufijo y reintenta. Mantén la longitud máxima observada.