Este desafío se trata de escribir código para resolver el siguiente problema.
Dadas dos cadenas A y B, su código debería generar los índices de inicio y finalización de una subcadena de A con las siguientes propiedades.
- La subcadena de A también debe coincidir con alguna subcadena de B con hasta una sustitución de un solo carácter en la cadena.
- Ya no debería haber una subcadena de A que satisfaga la primera propiedad.
Por ejemplo:
A = xxxappleyyyyyyy
B = zapllezzz
La subcadena apple
con índices 4 8
(indexación desde 1) sería una salida válida.
Puntuación
El puntaje de su respuesta será la suma de la longitud de su código en bytes + el tiempo en segundos que le toma a mi computadora cuando se ejecuta en las cadenas A y B de 1 millón de longitud cada una.
Prueba y entrada
Ejecutaré su código en dos cadenas de longitud 1 millón tomadas de las cadenas en http://hgdownload.cse.ucsc.edu/goldenPath/hg38/chromosomes/
La entrada estará en entrada estándar y será simplemente dos cadenas, separadas por una nueva línea.
Idiomas y bibliotecas
Puede usar cualquier idioma que tenga un compilador / intérprete / etc. para Linux y cualquier biblioteca que también sea de código abierto y esté disponible gratuitamente para Linux.
Mi máquina Los tiempos se ejecutarán en mi máquina. Esta es una instalación estándar de ubuntu en un procesador AMD FX-8350 de ocho núcleos. Esto también significa que necesito poder ejecutar su código. Como consecuencia, solo use software gratuito fácilmente disponible e incluya instrucciones completas sobre cómo compilar y ejecutar su código.
fuente
if(hash(str1 == test1 && str2 == test2)) print("100,150") else ..
- pensamientos?appley
necesita dos sustituciones para que coincidaapllez
. ¿Tal vez te perdiste que estáapll
en B y noappl
?Respuestas:
Tiempo C ++: O (n ^ 2), espacio extra: O (1)
Se necesitan 0.2s para completar los datos de 15K en mi máquina.
Para compilarlo, use:
Para ejecutarlo, use:
Explicación
La idea es simple, para string
s1
ys2
, tratamos de compensarlos2
pori
:Cuando el desplazamiento es 3:
Luego, para cada desplazamiento
i
, realizamos una exploración de programación dinámica ens1[i:]
ys2
. Para cada unoj
,f[j, 0]
sea la longitud máximad
tal ques1[j - d:j] == s2[j - i - d: j - i]
. Del mismo modo, dejef[j, 1]
que la longitud máxima sead
tal que las cadenass1[j - d:j]
ys2[j - i - d:j - i]
difieran en a lo sumo 1 carácter.Entonces
s1[j] == s2[j - i]
, tenemos:De otra manera:
Y:
Como solo necesitamos f [j - 1,:] para calcular f [j,:], solo se utiliza O (1) espacio extra.
Finalmente, la longitud máxima será:
Código
fuente
C ++
Traté de pensar en un buen algoritmo para hacer esto, pero hoy estoy un poco distraído y no se me ocurre nada que funcione bien. Esto se ejecuta en el tiempo O (n ^ 3), por lo que es muuuy lento. La otra opción en la que pensé podría haber sido teóricamente más rápida, pero habría ocupado el espacio O (n ^ 2), y con entradas de 1M, incluso hubiera sido peor.
Es vergonzoso, toma 190 segundos para entradas de 15K. Intentaré mejorarlo. Editar: Se agregó multiprocesamiento. Ahora toma 37 segundos para una entrada de 15K en 8 hilos.
fuente
i < a.length()
quei < a.length - (longestA.second - longestA.first)
(lo mismo para jy b.length ()), ya que no tendrá que procesar los partidos más pequeño que el actual más largaR
Parece que terminé de complicar el problema con la solución anterior. Esto es aproximadamente un 50% más rápido (23 segundos en cadenas de 15k) que el anterior y bastante simple.
Esto nunca será un competidor debido al idioma, pero me divertí un poco haciéndolo.
No estoy seguro de la complejidad de la misma, pero en un par de ~ 15k cadenas tarda 43 segundos usando un solo hilo. La mayor parte de eso fue la clasificación de las matrices. Intenté algunas otras bibliotecas, pero sin una mejora significativa.
Método:
fuente