Herramientas de usuario
algoritmos-oia:maxima-subsecuencia-palindromica
Diferencias
Muestra las diferencias entre dos versiones de la página.
| Próxima revisión | Revisión previa | ||
|
algoritmos-oia:maxima-subsecuencia-palindromica [2017/12/10 15:32] sebach creado |
algoritmos-oia:maxima-subsecuencia-palindromica [2017/12/10 15:33] (actual) 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]$. | ||
| Línea 48: | Línea 48: | ||
| if(s[i]==s[j]){ | if(s[i]==s[j]){ | ||
| tabla[i][j]=tabla[i+1][j-1]+2; | tabla[i][j]=tabla[i+1][j-1]+2; | ||
| - | else{ | + | }else{ |
| tabla[i][j]=max(tabla[i][j-1], tabla[i+1][j]); | tabla[i][j]=max(tabla[i][j-1], tabla[i+1][j]); | ||
| } | } | ||
algoritmos-oia/maxima-subsecuencia-palindromica.1512919935.txt.gz · Última modificación: 2017/12/10 15:32 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
