## 2.2.3 CÁLCULO DE LA SUB-SECUENCIA COMÚN MÁS LARGA

Una subsecuencia común más larga (LCS) de otra secuencia es la misma secuencia quitándole cero o más elementos. Dada la secuencia X = <x1, x2, ...,xm>, otra secuencia Z = <z1, z2, ..., zk> es una subsecuencia de X si existe una secuencia creciente <i1, i2, ..., ik> (no necesariamente contiguos) de índices de X tal que para cada j = 1,2, …, k, tenemos que xij = zj .

Ejemplo

Z = <B, C, D, B> es subsecuencia de X = <A, B, C, B, D, A, B>, con la secuencia de índices <2, 3, 5, 7>. Dadas las secuencias X y Y, Z es una secuencia común de X e Y si Z es una subsecuencia de ambas.

X = <A, B, C, B, D, A, B>, Y = <B, D, C, A, B, A>, la secuencia <B, C, A> es una subsecuencia común de X e Y. La secuencia es una LCS de X e Y, igual que <B, D, A, B>.

Dadas dos secuencias X e Y, encontramos la subsecuencia común máxima de X e Y.

Solución por fuerza bruta

- 2m subsecuencias de X a buscar en Y.
- Cada secuencia es un conjunto de índices {1, 2, …, m}.
- Tiempo exponencial.
- No práctico para secuencias largas.

Solución con programación dinámica

Subestructura óptima

Definir Dado X = <x1, x2, ...,xm>, el iésimo prefijo de X, i = 0, …, m, es Xi =<x1, x2, ...,xi> . X0 está vacío.

Teorema

Sean X = y Y = secuencias y Z = sea cualquier LCS de X y Y.

1. Si xm = yn, entonces zk = xm = yn y Zk-1 es una LCS de Xm-1 y Yn-1

2. Si xm ≠ yn, entonces zk ≠ xm implica que Z es una LCS de Xm-1 y Y.

3. Si xm ≠ yn, entonces zk ≠ ym implica que Z es una LCS de X y Yn-1

Por tanto, el problema de LCS tiene subestructura óptima.

La subestructura óptima del problema LCS nos lleva a la siguiente fórmula recursiva:

c[i,j]= 0 si i=0 o j=0;

c[i-1,j-1] + 1 si i,j > 0 y xi= yj;

max (c[i,j-1], c[i-1,j] si i,j > 0 y xi ≠ yj

###