Longest Common Substring

Q: ¿Cuál es la complejidad temporal de la subcadena común más larga?

La solución de programación dinámica tarda O(n × m) y requiere O(m) de memoria con una sola fila. Extender desde cada par de inicios requiere O(n × m × min(n, m)) en el peor de los casos. Un autómata de sufijos alcanza aproximadamente O(n + m) , a costa de un programa mucho más largo.

Q: ¿Cómo devuelves la subcadena común más larga en sí?

Siempre que una celda supere a best , registra también la posición i de s1 donde termina ese bloque. Al final, la subcadena son las letras de s1 correspondientes a best que terminan ahí. Una comparación estricta de mayor que conserva el primer bloque más largo encontrado en s1 .

MedioProgramación dinámica

+10

Recibes dos cadenas, s1 y s2. Una subcadena es una secuencia ininterrumpida de letras tomadas de una cadena, como ork de clockwork. Encuentra la subcadena más larga que s1 y s2 tienen en común y devuelve su longitud. Cuando ninguna letra aparece en ambas cadenas, la respuesta es 0.

Función

longestCommonSubstring(s1: string, s2: string) → integer

s1string: la primera cadena
s2string: la segunda cadena
Devuelveinteger: la longitud del bloque más largo de letras que se encuentra en ambas cadenas

Restricciones

1 ≤ s1.length ≤ 1000
1 ≤ s2.length ≤ 1000
s1 y s2 están formadas por letras minúsculas del alfabeto inglés.

Ejemplos

Entrada: s1 = "clockwork"s2 = "workshop"
Salida: 4
Explicación: work cierra clockwork y abre workshop, así que es una subcadena común de longitud 4, y no aparece ningún bloque más largo en ambas.

Entrada: s1 = "hammer"s2 = "harmed"
Salida: 2
Explicación: ha y me aparecen en ambas palabras, pero no hay ninguna secuencia de tres letras. Ambas palabras contienen h, a, m, e en ese orden, pero harmed tiene una r entre la a y la m.

Para ir más allá

¿Puedes comprobar si existe una subcadena común de una longitud determinada L en aproximadamente O(n + m) de tiempo con un hash rodante y después hacer una búsqueda binaria sobre L?

Pistas

Ábrelas de una en una. Cada una revela un poco más.

0 de 3 abiertas

Solución

Extender una coincidencia desde cada par de inicios vuelve a leer las mismas letras. Fíjate en dónde termina un bloque: el bloque común que termina en s1[i] y s2[j] tiene una letra más que el que termina en las dos letras anteriores, o está vacío si las letras son distintas. Una tabla de estas longitudes da la respuesta en tiempo O(n × m).

Extiéndete desde cada par de posiciones iniciales

Correcto, pero no termina con las pruebas más grandes

Intuición

Todo subcadena común empieza en alguna posición i de s1 y en alguna posición j de s2. Para cada par, avanza mientras las letras coincidan y cuenta los pasos; el mayor recuento es la respuesta.

El texto repetitivo hace que los recorridos sean largos. Cuando ambas cadenas son 1000 copias de a, cada par recorre el sufijo más corto hasta el final: unas 3.3 × 10^8 comparaciones de letras. El recorrido desde (i, j) repite todo el recorrido desde (i+1, j+1), una letra más adelante.

Algoritmo

Establece best = 0.
Para cada i en s1 y cada j en s2, establece k = 0.
Mientras tanto i+k como j+k estén dentro de sus cadenas y s1[i+k] == s2[j+k], suma 1 a k.
Conserva el valor más grande de k en best y devuélvelo.

def longestCommonSubstring(s1, s2):
    n, m = len(s1), len(s2)
    best = 0
    for i in range(n):
        for j in range(m):
            # Walk forward while the two strings agree
            k = 0
            while i + k < n and j + k < m and s1[i + k] == s2[j + k]:
                k += 1
            if k > best:
                best = k
    return best

Tabla de longitudes de bloque que terminan en cada par

Intuición

Sea run[i][j] la longitud del bloque común más largo que termina exactamente en s1[i-1] y s2[j-1]; la fila 0 y la columna 0 contienen 0. Ese bloque debe contener ambas letras. Si son diferentes, no existe ningún bloque y la celda es 0. Si coinciden, el bloque es este par más el bloque que termina una letra antes en ambas cadenas: run[i-1][j-1] + 1. Cada subcadena común termina en algún lugar, así que la respuesta es la celda más grande, dondequiera que esté.

Para hammer y harmed, las h dan 1 y las a lo extienden a 2; después, la r rompe el bloque. La segunda m de hammer coincide con la m de harmed después de una discrepancia entre m y r, así que empieza en 1, y las e lo elevan a 2. Ninguna celda llega a 3.

Una comparación por celda: alrededor de un millón para dos cadenas de 1000 letras, sea cual sea el texto.

Algoritmo

Asigna run con n+1 filas y m+1 columnas, todas con valor 0, y establece best = 0.
Recorre i de 1 a n y, dentro de ese bucle, j de 1 a m, comparando s1[i-1] con s2[j-1].
Si coinciden, establece run[i][j] = run[i-1][j-1] + 1 y actualiza best.
Si no coinciden, deja la celda en 0.
Devuelve best.

def longestCommonSubstring(s1, s2):
    n, m = len(s1), len(s2)
    # run[i][j]: length of the longest block that ends at s1[i-1] and at s2[j-1]
    run = [[0] * (m + 1) for _ in range(n + 1)]
    best = 0
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if s1[i - 1] == s2[j - 1]:
                run[i][j] = run[i - 1][j - 1] + 1
                if run[i][j] > best:
                    best = run[i][j]
            # a mismatch leaves run[i][j] at 0
    return best

Una fila, actualizada de derecha a izquierda

Intuición

Cada celda lee únicamente la celda situada en diagonal, arriba y a la izquierda. Así, un único arreglo run de m+1 números puede contener la tabla si recorres j de derecha a izquierda: cuando escribes run[j], la posición run[j-1] todavía contiene el valor de la fila anterior para la letra de s1, que es la celda diagonal.

Ahora, una discrepancia debe escribir explícitamente 0, porque la posición todavía contiene un número de la fila anterior. El tiempo sigue siendo O(n × m) y la memoria baja de unos 10^6 números a 1001.

Algoritmo

Crea un arreglo run de m+1 ceros y establece best = 0.
Para cada letra ch de s1, recorre j desde m hasta 1.
Si ch == s2[j-1], establece run[j] = run[j-1] + 1 y actualiza best.
De lo contrario, establece run[j] = 0.
Devuelve best.

def longestCommonSubstring(s1, s2):
    m = len(s2)
    # run[j]: length of the common block that ends at the current letter of s1 and at s2[j-1]
    run = [0] * (m + 1)
    best = 0
    for ch in s1:
        # Right to left, so run[j-1] still holds the value from the previous letter of s1
        for j in range(m, 0, -1):
            if ch == s2[j - 1]:
                run[j] = run[j - 1] + 1
                if run[j] > best:
                    best = run[j]
            else:
                run[j] = 0
    return best

Errores comunes y casos límite

Devolver la última celda. run[n][m] solo abarca bloques que terminan en ambas últimas letras. Para abc y abd da 0, mientras que ab da 2.
Copiar el vecino más grande cuando hay una discrepancia. Esa es la regla de subsecuencia, y permite que un bloque omita letras: para hammer y harmed da 4 en lugar de 2.
Recorrer la única fila de izquierda a derecha. El valor diagonal se sobrescribe antes de leerlo, así que comparar a con aa da 2.
Omitir el reinicio en la única fila. Una longitud de la letra anterior de s1 se conserva y luego extiende un bloque que no está ahí.
Recorrer la fuerza bruta sin comprobar los límites. Para zzzz y zz, se lee más allá del final de la cadena más corta.

Preguntas frecuentes3

¿Cuál es la diferencia entre la subcadena común más larga y la subsecuencia común más larga?

Una subcadena es una secuencia ininterrumpida de letras; una subsecuencia mantiene el orden, pero puede tener huecos. Para hammer y harmed, la subcadena común más larga tiene una longitud de 2 y la subsecuencia común más larga tiene una longitud de 4 (hame). En las tablas, una discrepancia restablece a 0 la celda de la subcadena, pero hace que la celda de la subsecuencia copie el vecino de mayor valor.

¿Cuál es la complejidad temporal de la subcadena común más larga?

La solución de programación dinámica tarda O(n × m) y requiere O(m) de memoria con una sola fila. Extender desde cada par de inicios requiere O(n × m × min(n, m)) en el peor de los casos. Un autómata de sufijos alcanza aproximadamente O(n + m), a costa de un programa mucho más largo.

¿Cómo devuelves la subcadena común más larga en sí?

Siempre que una celda supere a best, registra también la posición i de s1 donde termina ese bloque. Al final, la subcadena son las letras de s1 correspondientes a best que terminan ahí. Una comparación estricta de mayor que conserva el primer bloque más largo encontrado en s1.

def longestCommonSubstring(s1, s2):
    # Escribe el código aquí

Prueba #1

Prueba #2

Prueba #3

Argumentos

s1 = "clockwork"
s2 = "workshop"

Salida Esperada

Longest Common Substring

Función

Restricciones

Ejemplos

Pistas

Solución

Extiéndete desde cada par de posiciones iniciales

Tabla de longitudes de bloque que terminan en cada par

Una fila, actualizada de derecha a izquierda

Errores comunes y casos límite

Preguntas frecuentes3

Problemas similares