Los códices gemelos
- O(n²) · Muy difícil
- Plan completo
- Python
- JavaScript
- ciclos
- textos
- índices
Enunciado
Del incendio de la abadía se salvaron dos copias del mismo códice. Las hicieron copistas distintos, y cada uno se saltó o cambió letras a su manera. Fray Bernardo, el bibliotecario, quiere medir el pasaje más largo que las dos copias conservan idéntico: de ese, al menos, puede fiarse. Escribe una función que reciba a y b, dos textos de letras minúsculas sin espacios (pueden venir vacíos), y regrese, como entero, el largo del trozo de letras seguidas más largo que aparece tal cual en los dos. Puede estar en cualquier lugar de cada texto, pero no se vale saltarse letras: tiene que ir seguido en a y seguido en b.
Con "pergamino" y "camino": "amino" empieza en la quinta letra de a y en la segunda de b, mide 5, y no hay un trozo común de 6, así que regresa 5. Con "abxabcd" y "abcd", "ab" coincide desde el principio, pero "abcd" es más largo: regresa 4.
Si no comparten ninguna letra, o alguno viene vacío, regresa 0.
Ejemplos
El ejemplo
"pergamino", "camino" → 5
El primer trozo común no es el más largo
"abxabcd", "abcd" → 4
No comparten ninguna letra
"abc", "xyz" → 0
Las dos copias son idénticas
"salmo", "salmo" → 5
No se vale saltarse letras
"abcde", "azbzczdze" → 1
Además de estas, el reto tiene pruebas ocultas que se revelan al enviar tu solución.
Empiezas con esto
Python
def pasaje_comun(a, b):
passJavaScript
function pasajeComun(a, b) {
}Se abre en el navegador, con el editor y las pruebas. Este reto es del plan completo; los de O(1) y O(log n) son gratis.
Más retos de O(n²)
- Los dulces del campamentolistas · ciclos · comparaciones
- Los gritos de la entrenadoraciclos · listas · textos
- Los guerreros de Cadmolistas · ciclos · comparaciones
- Los hot cakes de Don Chuyciclos · listas · índices
- Los papeles que no se cruzanconjuntos · listas · ordenar
- Los tres costaleslistas · ordenar · ciclos