Planteamiento y cuándo se aplica
Un arreglo de sufijos almacena el índice inicial de cada sufijo, ordenado lexicográficamente. Cuando un texto fijo recibe muchas consultas de patrones, este índice encuentra coincidencias sin volver a escanear desde el principio. Stanford CS166 pide a los candidatos implementar searchFor, devolver cada coincidencia y contabilizar el tamaño de la salida; aquí m es la longitud del patrón, n es la longitud del texto y z es el número de resultados.
Qué está evaluando el entrevistador
- Explicar que la aparición de un patrón es un sufijo cuyo prefijo coincide con el patrón.
- Encontrar los límites izquierdo y derecho con cotas inferiores (lower bounds) en lugar de detenerse en una sola coincidencia.
- Separar el costo de construcción único del costo por consulta y asignar O(z) para la salida.
- Manejar patrones vacíos, centinelas, sufijos duplicados y el costo de comparación de caracteres.
Aclaraciones a preguntar primero
- ¿El texto es fijo y se consulta muchas veces? Si cambia con frecuencia, reconstruir un arreglo de sufijos puede no ser adecuado.
- ¿La respuesta debe devolver todas las posiciones de inicio, solo el conteo o solo la existencia?
- ¿Están definidos el uso de mayúsculas/minúsculas, la normalización de Unicode y el ordenamiento a nivel de bytes? El comparador debe ajustarse al contrato.
- ¿El arreglo de sufijos ya viene provisto o debe construirse? Si se requiere construirlo, ¿es aceptable un ordenamiento didáctico o se espera una construcción en tiempo lineal?
Una respuesta de 30 segundos
“Los sufijos están ordenados, por lo que todos los sufijos que comienzan con pattern forman un único intervalo continuo. Comparo el patrón con text[sa[i]:] por prefijo, uso una búsqueda binaria para el primer sufijo no menor que el patrón y otra para el primer sufijo estrictamente posterior a ese prefijo. Cada valor de sa en el intervalo es una coincidencia, por lo que reportarlo cuesta O(z) y la consulta es O(m log n + z). Por convención, un patrón vacío devuelve n+1 posiciones.”
Solución paso a paso
Paso 1: Definir el significado del arreglo de sufijos
Para banana, los inicios de los sufijos en orden lexicográfico son [5, 3, 1, 0, 4, 2]. El arreglo almacena inicios enteros, no copias de cadenas de sufijos. Las notas del MIT describen exactamente este índice lexicográfico y el uso de búsqueda binaria.
Paso 2: Convertir la coincidencia en un intervalo
Todos los sufijos que comienzan con ana son adyacentes, por lo que la respuesta es un intervalo semiabierto [left, right). El comparador necesita tres resultados: el prefijo del sufijo es menor, igual o mayor que el patrón. Ante la igualdad, aún se debe buscar a la izquierda y a la derecha para capturar cada aparición.
Paso 3: Implementar dos cotas inferiores (lower bounds)
El primer lower bound busca el primer prefijo de sufijo que no sea menor que el patrón. El segundo busca el primer prefijo de sufijo estrictamente mayor que este, o encuentra el extremo derecho del rango igual. Comparar el patrón con un sufijo completo es incorrecto: un sufijo más corto que sea un prefijo del patrón debe considerarse menor.
Paso 4: Elecciones de complejidad y construcción
Con un arreglo de sufijos provisto, cada comparación examina a lo sumo m caracteres y la búsqueda binaria realiza O(log n) comparaciones, por lo que la consulta es O(m log n + z). Stanford separa explícitamente el costo de reporte O(z). Una construcción didáctica puede ordenar rebanadas (slices) de sufijos, pero copia datos y es lenta; en producción se debe usar duplicación de prefijos (prefix doubling), SA-IS o una biblioteca validada. Los materiales del MIT y Stanford posicionan a los arreglos de sufijos como índices de texto fijo que ahorran el alto espacio en punteros en comparación con los árboles de sufijos.
Implementación ejecutable en Python
def build_suffix_array(text):
# Teaching build for verification, not a production complexity claim.
return sorted(range(len(text)), key=lambda start: text[start:])
def compare_suffix_prefix(text, start, pattern):
suffix = text[start:]
prefix = suffix[:len(pattern)]
if prefix < pattern:
return -1
if prefix > pattern:
return 1
if len(suffix) < len(pattern):
return -1
return 0
def search_with_suffix_array(text, suffix_array, pattern):
if pattern == "":
return list(range(len(text) + 1))
def lower_bound(strict):
lo, hi = 0, len(suffix_array)
while lo < hi:
mid = (lo + hi) // 2
cmp = compare_suffix_prefix(text, suffix_array[mid], pattern)
take_right = cmp < 0 or (strict and cmp == 0)
if take_right:
lo = mid + 1
else:
hi = mid
return lo
left = lower_bound(strict=False)
right = lower_bound(strict=True)
return sorted(suffix_array[left:right])El código separa la construcción de las consultas. El ordenamiento final devuelve los inicios en el orden del texto; omítelo si el contrato de la API estipula el orden del arreglo de sufijos. Texto vacío, patrón vacío, sin coincidencia y coincidencias repetidas son casos de prueba directos.
Una respuesta de muestra de alta calidad
“Primero confirmo que el texto es fijo y recibe muchos patrones; luego almaceno cada inicio de sufijo en orden lexicográfico. Dado que un patrón es un prefijo común de los sufijos coincidentes, todas las respuestas ocupan un rango continuo. Dos cotas inferiores encuentran ese rango; las comparaciones inspeccionan solo la longitud del patrón y tratan a un sufijo más corto como menor. Dado el arreglo, la consulta es O(m log n + z), donde z es la salida. Una construcción educativa puede usar ordenamiento, pero un índice grande necesita duplicación de prefijos, SA-IS o una implementación validada, con una política definida de normalización de caracteres.”
Errores comunes
- Devolver la primera coincidencia → se pierden apariciones adyacentes → aplicar búsqueda binaria en ambos límites.
- Comparar cadenas de sufijos completas con el patrón → los límites de sufijos cortos son incorrectos → definir la comparación de prefijos y la regla del sufijo más corto.
- Cargar la construcción a cada consulta → no se explica el escenario de texto fijo → reportar por separado los costos de construcción única y por consulta.
- Llamar orden del texto al intervalo del arreglo de sufijos → el llamador ve un orden inestable → ordenar los inicios cuando sea necesario o documentar el orden.
- Olvidar las n+1 posiciones del patrón vacío → se viola el contrato establecido → manejar primero el patrón vacío.
Preguntas de seguimiento y respuestas sólidas
¿Cómo reduces las comparaciones repetidas de caracteres para un patrón largo?
Agrega información de LCP (Longest Common Prefix) para sufijos vecinos y reutiliza prefijos comunes conocidos durante la búsqueda binaria. Esto puede aproximarse a O(m + log n), pero requiere estado de LCP adicional e invariantes más fuertes; sin esto, declara O(m log n) honestamente.
¿Usarías un arreglo de sufijos si el texto cambia frecuentemente?
No como un único índice estático. Reconstrucciones por lotes, índices a nivel de segmento con fusiones posteriores o un algoritmo de coincidencia en línea pueden ajustarse mejor. Se debe elegir según la tasa de actualización, el volumen de consultas y el retraso de reconstrucción aceptable.
¿Cómo pruebas que los límites de la búsqueda binaria sean correctos?
Compara contra escaneos por fuerza bruta en textos y patrones pequeños aleatorios. Incluye patrones vacíos, caracteres repetidos, patrones más largos que el texto, casos sin coincidencias y casos donde coincida cada posición. Valida con aserciones que las posiciones vecinas fuera del rango no cumplan el predicado del prefijo.
¿Por qué no usar KMP directamente?
Para un solo patrón y una sola pasada sobre el texto, KMP es más simple con O(n+m). Un arreglo de sufijos vale la pena para muchos patrones en texto fijo y para operaciones fuera de línea que involucran subcadenas repetidas, LCP o BWT.