Herramientas de usuario
algoritmos-oia:maxima-subsecuencia-palindromica
Diferencias
Muestra las diferencias entre dos versiones de la página.
| Última revisión Ambos lados, revisión siguiente | |||
|
algoritmos-oia:maxima-subsecuencia-palindromica [2017/12/10 15:32] sebach creado |
algoritmos-oia:maxima-subsecuencia-palindromica [2017/12/10 15:32] sebach |
||
|---|---|---|---|
| Línea 18: | Línea 18: | ||
| Entonces, al principio tenemos $tabla[i][i]=1$. Y para longitud $2$, tenemos que $tabla[i][i+1]$ vale $2$ si $s[i]$ es igual a $s[i+1]$, y si no vale $1$. | Entonces, al principio tenemos $tabla[i][i]=1$. Y para longitud $2$, tenemos que $tabla[i][i+1]$ vale $2$ si $s[i]$ es igual a $s[i+1]$, y si no vale $1$. | ||
| - | Ahora, supongamos que ya tenemos los valores de $tabla[i][i+k]$ para $k=1, 2, ..., m$. Cómo calculamos los valores de $tabla[i][i+m+1]$? | + | Ahora, supongamos que ya tenemos los valores de $tabla[i][i+k]$ para $k=0, 1, 2, ..., m$. Cómo calculamos los valores de $tabla[i][i+m+1]$? |
| Si $s[i]$ es igual a $s[i+m+1]$, entonces la subsecuencia más larga tendrá a estos caracteres como borde, y luego adentro se sumará la subsecuencia más larga, que está guardada en $tabla[i+1][i+m]$. | Si $s[i]$ es igual a $s[i+m+1]$, entonces la subsecuencia más larga tendrá a estos caracteres como borde, y luego adentro se sumará la subsecuencia más larga, que está guardada en $tabla[i+1][i+m]$. | ||
algoritmos-oia/maxima-subsecuencia-palindromica.txt · Última modificación: 2017/12/10 15:33 por sebach
Herramientas de la página
Excepto donde se indique lo contrario, el contenido de este wiki esta bajo la siguiente licencia: Public Domain
