Herramientas de usuario
algoritmos-oia:maxima-longitud-de-substring-palindromica
Diferencias
Muestra las diferencias entre dos versiones de la página.
|
algoritmos-oia:maxima-longitud-de-substring-palindromica [2017/12/10 15:06] sebach creado |
algoritmos-oia:maxima-longitud-de-substring-palindromica [2017/12/10 15:21] (actual) sebach [Con un poco de programación dinámica] |
||
|---|---|---|---|
| Línea 9: | Línea 9: | ||
| ==== Con un poco de programación dinámica ==== | ==== Con un poco de programación dinámica ==== | ||
| - | Con programación dinámica, podemos reducir el tiempo fácilmente a $O(n^2)$. Lo que haremos será guardar en una tabla de dos dimensiones $vector< vector<int> > tabla$, $tabla[i][j]$ va a ser true si y solo si la substring desde $i$ hasta $j$ inclusive es un palíndromo. | + | Con programación dinámica, podemos reducir el tiempo fácilmente a $O(n^2)$. Lo que haremos será guardar en una tabla de dos dimensiones $vector< vector<bool> > tabla$, $tabla[i][j]$ va a ser true si y solo si la substring desde $i$ hasta $j$ inclusive es un palíndromo. |
| Empezamos poniendo a mano los palíndromos de longitud $1$ (todos) y $2$, y partir de ahí, $tabla[i][j]$ será true si las posiciones $i$ y $j$ de la string son iguales, y además $tabla[i+1][j]$ es true: | Empezamos poniendo a mano los palíndromos de longitud $1$ (todos) y $2$, y partir de ahí, $tabla[i][j]$ será true si las posiciones $i$ y $j$ de la string son iguales, y además $tabla[i+1][j]$ es true: | ||
| Línea 17: | Línea 17: | ||
| // Dada una string s | // Dada una string s | ||
| int n=s.size(); | int n=s.size(); | ||
| - | vector< vector<int> > tabla(n, vector<int>(n, false)); | + | vector< vector<bool> > tabla(n, vector<bool>(n, false)); |
| int maxLength=1, start=0; //guardamos la maxima longitud hasta el momento, y donde empieza la misma | int maxLength=1, start=0; //guardamos la maxima longitud hasta el momento, y donde empieza la misma | ||
algoritmos-oia/maxima-longitud-de-substring-palindromica.1512918400.txt.gz · Última modificación: 2017/12/10 15:06 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
