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.
- Ya no debería haber una subcadena de A que satisfaga la primera propiedad.
Por ejemplo:
A = xxxappleyyyyyyy
B = zapplezzz
La subcadena apple
con índices 4 8
(indexación desde 1) sería una salida válida.
Funcionalidad
Puede suponer que la entrada estará en el estándar o en un archivo en el directorio local, esa es su elección. El formato del archivo será simplemente dos cadenas, separadas por una nueva línea. La respuesta debe ser un programa completo y no solo una función.
Eventualmente me gustaría probar su código en dos subcadenas tomadas de las cadenas en http://hgdownload.cse.ucsc.edu/goldenPath/hg38/chromosomes/ .
Puntuación
Este es el código de golf con un toque diferente. Su código debe ejecutarse a O(n)
tiempo, donde n
es la longitud total de la entrada.
Idiomas y bibliotecas
Puede usar cualquier idioma que tenga un compilador / intérprete / etc. para Linux Solo debe usar bibliotecas de código abierto estándar no diseñadas para resolver esta tarea. En caso de disputa, contaré esto como cualquier biblioteca que viene como estándar con su idioma o una que puede instalar en una máquina ubuntu predeterminada desde un repositorio predeterminado.
Información útil
Hay al menos dos formas de resolver este problema en tiempo lineal. Una es calcular primero el árbol de sufijos y la segunda es calcular primero la matriz de sufijos y la matriz LCP.
- Aquí hay una explicación completa y (tal vez demasiado) detallada de la construcción del árbol de sufijos de tiempo lineal (resulta que algunas de las figuras están en mal estado lamentablemente). También hay una muy buena respuesta SO sobre la construcción del árbol de sufijos de tiempo lineal en https://stackoverflow.com/questions/9452701/ukkonens-suffix-tree-algorithm-in-plain-english . Incluye un enlace al código fuente también. Aquí se puede encontrar otra explicación detallada , esta vez dando una solución completa en C.
- La Sección 2 de http://www.cs.cmu.edu/~guyb/realworld/papersS04/KaSa03.pdf proporciona un algoritmo de construcción de matriz de sufijo de tiempo lineal y el Apéndice A tiene código fuente C ++. Esta respuesta le indica cómo calcular la subcadena común más larga https://cs.stackexchange.com/questions/9555/computing-the-longest-common-substring-of-two-strings-using-suffix-arrays . Sección 5 de https://courses.csail.mit.edu/6.851/spring12/scribe/lec16.pdf que también tiene una conferencia de video asociada https://courses.csail.mit.edu/6.851/spring12/lectures/L16 .html también explica el mismo algoritmo a partir de las 1:16:00.
fuente
O(n) time
¿Estás seguro de que es posible?Respuestas:
Python 2, 646 bytes
Utiliza el algoritmo de inclinación descrito en "Construcción de matriz de sufijo de trabajo lineal simple" de Kärkkäinen y Sanders. La implementación de C ++ incluida en ese documento ya se siente un poco "golf", pero todavía hay mucho espacio para acortarla. Por ejemplo, podemos recurrir hasta llegar a una matriz de longitud uno, en lugar de cortocircuito como en el documento, sin violar el
O(n)
requisito.Para la parte de LCP, seguí "Cálculo de prefijo común más largo de tiempo lineal en matrices de sufijos y sus aplicaciones" por Kusai et al.
El programa emite
1 0
si la subcadena común más larga está vacía.Aquí hay un código de desarrollo que incluye una versión anterior del programa que sigue la implementación de C ++ un poco más de cerca, algunos enfoques más lentos para la comparación y un simple generador de casos de prueba:
fuente