Longest Common Subsequence

E
L
L
Y 18 más contribuidores
```"""
LCS Problem Statement: Given two sequences, find the length of longest subsequence
present in both of them.  A subsequence is a sequence that appears in the same relative
order, but not necessarily continuous.
Example:"abc", "abg" are subsequences of "abcdefgh".
"""

def longest_common_subsequence(x: str, y: str):
"""
Finds the longest common subsequence between two strings. Also returns the
The subsequence found

Parameters
----------

x: str, one of the strings
y: str, the other string

Returns
-------
L[m][n]: int, the length of the longest subsequence. Also equal to len(seq)
Seq: str, the subsequence found

>>> longest_common_subsequence("programming", "gaming")
(6, 'gaming')
>>> longest_common_subsequence("physics", "smartphone")
(2, 'ph')
>>> longest_common_subsequence("computer", "food")
(1, 'o')
"""
# find the length of strings

assert x is not None
assert y is not None

m = len(x)
n = len(y)

# declaring the array for storing the dp values
L = [[0] * (n + 1) for _ in range(m + 1)]

for i in range(1, m + 1):
for j in range(1, n + 1):
if x[i - 1] == y[j - 1]:
match = 1
else:
match = 0

L[i][j] = max(L[i - 1][j], L[i][j - 1], L[i - 1][j - 1] + match)

seq = ""
i, j = m, n
while i > 0 and j > 0:
if x[i - 1] == y[j - 1]:
match = 1
else:
match = 0

if L[i][j] == L[i - 1][j - 1] + match:
if match == 1:
seq = x[i - 1] + seq
i -= 1
j -= 1
elif L[i][j] == L[i - 1][j]:
i -= 1
else:
j -= 1

return L[m][n], seq

if __name__ == "__main__":
a = "AGGTAB"
b = "GXTXAYB"
expected_ln = 4
expected_subseq = "GTAB"

ln, subseq = longest_common_subsequence(a, b)
print("len =", ln, ", sub-sequence =", subseq)
import doctest

doctest.testmod()
```

Declaración de problema

Dadas dos cadenas `S` y `T`, busque la longitud de la subsecuencia común más larga (LCS).

Enfoque

Que el `dp[i][j]` sea la longitud de la subsecuencia común más larga de los prefijos `S[1..i]` y `T[1..j]`. Nuestra respuesta (la longitud de LCS) es `dp[| S|] [| T|]`, ya que el prefijo de la longitud de la cadena es la propia cadena.

Tanto `dp[0][i]` como `dp[i][0]` son `0` para cualquier `i`, desde el LCS de prefijo vacío y cualquier otra cosa es una cadena vacía.

Ahora, vamos a tratar de calcular `dp[i][j]` para cualquier `i`, `j`. Digamos `S[1..i] = *A` y `T[1..j] = *B` donde `*` significa cualquier secuencia de letras (podría ser diferente para `S` y `T`), `A` significa cualquier letra y `B` significa cualquier letra diferente de `A`. Dado que `A != B`, nuestro LCS no incluye `A` o `B` como último carácter. Así que podríamos tratar de tirar a la distancia el personaje `A` o `B`. Si lanzamos `A`, nuestra longitud LCS será `dp[i - 1][j]` (ya que tenemos prefijos `S[1..i - 1]` y `T[1..j]`). Si intentamos lanzar el carácter `B`, tendremos prefijos `S[1..i]` y `T[1..j - 1]`, por lo que la longitud de LCS será `dp[i][j - 1]`. Mientras buscamos la subsecuencia común más larga, elegiremos el valor máximo de `dp[i][j - 1]` y `dp[i - 1] [j]`.

¿Pero qué pasa si `S[1..i] = *A` y `T[1..j] = *A`? Podríamos decir que el LCS de nuestros prefijos es LCS de prefijos `S[1..i - 1]` y `T[1..j - 1]` más la letra `A`. Así que `dp[i][j] = dp[i - 1][j - 1] + 1` es igual a `S[i] = T[j]`.

Pudimos ver que podemos llenar nuestra tabla `dp` fila por fila, columna por columna. Así que nuestro algoritmo será como:

• Digamos que tenemos cuerdas `S` de la longitud N y `T` de la longitud M (numeradas a partir de 1). Vamos a crear la tabla `dp` de tamaño `(N + 1) x (M + 1)` numerada a partir de 0.
• Vamos a llenar la 0ª fila y la 0ª columna de `dp` con 0.
• A continuación, seguimos el algoritmo:
``````for i in range(1..N):
for j in range(1..M):
if(S[i] == T[j])
dp[i][j] = dp[i - 1][j - 1] + 1
else
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
``````

`O(N * M)` - En cualquier caso

`O(N * M)` - implementación simple `O(min {N, M})` - implementación de dos capas (como `dp[i][j]` depende sólo de las capas i-th e i-th, coudld almacenamos sólo dos capas).

Ejemplo

Digamos que tenemos cuerdas `ABCB` y `BBCB`. Construiremos una mesa de este tipo:

``````# # Una B C B
# 0 0 0 0 0
B 0 ? ? ? ?
B 0 ? ? ? ?
C 0 ? ? ?
B 0 ? ? ? ?
``````

Ahora empezaremos a llenar nuestra mesa desde la 1ª fila. Puesto que `S[1] = A` y `T[1] = B`, `dp[1] [1]` será el valor máximo de `dp[0] [1] = 0` y `dp[1] [0] = 0`. Así que `dp[1] [1] = 0`. Pero ahora `S[2] = B = T[1]`, así que `dp[1] [2] = dp[0] [1] + 1 = 1`. `dp[1] [3]` es `1` desde `A != C` y elegimos `max{dp[1] [2], dp[0] [3]}`. Y `dp[1] [4] = dp[0] [3] + 1 = 1`.

``````# # A B C B
# 0 0 0 0 0
B 0 0 1 1 1
B 0 ? ? ? ?
C 0 ? ? ? ?
B 0 ? ? ? ?
``````

Ahora vamos a llenar la otra parte de la tabla:

``````# # A B C B
# 0 0 0 0 0
B 0 0 1 1 1
B 0 0 1 1 2
C 0 0 1 2 2
B 0 0 1 2 3
``````

Así que la longitud de LCS es `dp[4] [4] = 3`.