Sin precomputación o sin limitar el tamaño del prefijo: no es posible.
Con la precomputación, desearía comenzar con un enfoque de internamiento de cadena para poder determinar la identidad de la cadena en O (1), por ejemplo, cada cadena distinta tiene exactamente un puntero único.
Tendría que suponer que la entrada es una cadena interna. Si se trata de un valor para el que no conoce la cadena interna única correspondiente, lleva tiempo encontrarla.
- ¿Qué tipo de algoritmos se usaron en la generación de mapas aleatorios de los mapas de Age of Empires II?
- Cómo escribir un validador de sangría de Python
- ¿Cómo funciona el algoritmo de sugerencia de seguimiento de Twitter?
- Para una computadora, ¿qué tan aleatorio es ser aleatorio?
- ¿Cuál es la complejidad temporal de una función que calcula la altura de un árbol binario de forma recursiva? ¿Es O (N) u O (NlogN)?
Puede lograrlo trivialmente usando un espacio cuadrático para una tabla de búsqueda, en el número de cadenas. Pero puedes hacerlo mejor que eso.
Si almacena todas las cadenas en un árbol, donde cada nodo apunta a los hijos cuyo prefijo más largo es el padre, puede hacerlo mejor. Un enfoque simple sería un trie, y hay formas de comprimir el trie si de otra manera desperdiciara mucho espacio.
Entonces necesita alguna anotación almacenada en este árbol para admitir su búsqueda O (1) de relaciones ancestrales / descendientes.
Un enfoque (llamado esquema de numeración de Dietz, desarrollado para XML) es almacenar la numeración de pedidos anticipados y posteriores de cada nodo. Entonces puedes usar esta propiedad:
Para dos nodos dados x e y de un árbol T, x es un antecesor de y si y solo si x ocurre antes de y en el recorrido previo al pedido de T y después de y en el recorrido del orden posterior.
Si el número de búsquedas de prefijos >> el número de cadenas, podría mejorar el rendimiento general con este tipo de esquema de búsqueda O (1), a expensas del espacio y la preparación. Esto también supone que puede limitar el número de entradas de cadena, por lo que es una trampa porque no puede darle la respuesta hasta que tenga las cadenas preparadas de esta manera … pero esta es una restricción común en el mundo real. Las cosas están en la memoria de antemano.
Entonces puedes, pero solo si engañas un poco el significado de la pregunta. La respuesta directa es que no puedes.
