OIA-Wiki

Esta página es de solo lectura. Puedes ver la fuente pero no puedes cambiarla. Pregunta a tu administrador si crees que esto es incorrecto.
==== Problema =====

Encontrar el palíndromo más largo que es substring (caracteres consecutivos) de una string dada de longitud $n$.

==== Algoritmo ingenuo ====

Sin pensar mucho, algo poco eficiente pero muy fácil de ver es la solución en $O(n^3)$. Simplemente recorremos todos los índices de la string para fijar como borde izquierdo de la substring, recorremos de vuelta para fijar como borde derecho, y una vez fijados los bordes vamos recorriendo la substring dada y chequeamos si es palíndromo.

==== 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<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:

<code cpp longest-palindrome-substring-cuadratico.cpp>

// Dada una string s
int n=s.size();
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

for(int i=0; i<n; i++){
    tabla[i][i]=true;
}

for(int i=0; i<n; i++){
    if(s[i]==s[i+1]){
        tabla[i][i+1]=true;
        maxLength=2;
        start=i;
    }
}

for(int k=3; k<=n; k++){ // hacemos dinamica de abajo para arriba, vamos calculando los palindromos de longitudes k=3, 4, 5...
    for (int i = 0; i < n-k+1 ; ++i){
        int j = i + k - 1; // para que j no se pase de n-1 es que ponemos el limite raro en el for de i
        if (s[i] == s[j] && table[i+1][j-1]){
            table[i][j] = true;
            if (k > maxLength){
                start = i;
                maxLength = k;
            }
        }
    }
}
cout<<"mayor longitud: "<<maxLength<<endl;
cout<<"el palindromo es: ";
for(int i=start; i<start+maxLength; i++)cout<<s[i];

</code>


==== Otra de O(n^2) sin tanto tecnicismo ====

Algo que podemos hacer, que no requiere más que analizar el problema, es, en vez de buscar los bordes como en la primera idea, buscar los centros.
El centro de un posible palíndromo substring o bien es una de las letras, o bien está entre dos letras. Entonces hay $2*n$ posibles centro, y partir de un centro fijo, simplemente vamos viendo si las las letras a distancia $1$ del centro coinciden, si sí, las de distancia $2$, y así hasta que deje de ser un palíndromo, y actualizamos el valor de la máxima substring palíndromo.

<code cpp>

// Tenemos la string s
int n=s.size();

int maxLength=1, start=0;

for(int centro=0; centro<n; centro++){
    // ahora el centro o está en la letra, o entre dos letras
    for(int caso=0; caso<2; caso++){
        int left, right;
        if(caso==0){ //el centro es entre dos letras
            left=centro;
            right=centro+1;
        }else{ // el centro es en la letra "centro"
            left=centro-1;
            right=centro+1;
        }
        while(left>=0 && right<n && s[left]==s[right]){
            left--;
            right++;
        }
        // Si sali del while es porque ahora, [left...right] no es un palindromo, o left<0 o right>=n. Para encontrar entonces el palindromo mas largo tengo que "volver" al estado anterior:
        left++; right--;
        int palindromeLength=right-left+1;
        if(palindromeLength>maxLength){
            maxLength=palindromeLength;
            start=left;
        }
    }
}

</code>

Comentarios de este código:

1) Quizás está bueno mirar las posiciones borde, por ejemplo, cuando $centro$ vale $0$, en uno de los casos pasa que $left$ vale $-1$. Pero no pasa nada porque después corremos uno a ambos bordes y quedan en $0$ los dos, el palíndromo de un caracter. También, cuando $centro$ vale $n-1$, en el primer caso se tiene $left=n-1$, $right=n$. Al salir del while sin ninguna iteración, el algoritmo suma y resta $1$ y tiene $left=n$, $right=n-1$. Si bien esto no tiene sentido, la longitud de ese "palíndromo" daría $0$ y no pasaría nada.

2) Este es un clarísimo ejemplo de cómo pensar un poquito un problema, antes de salir a matar con todo lo que tengamos, sea dinámica o lo que sea, puede ser muy ventajoso.
Digamos, sin saber lo que es programación dinámica ni nada loco, el único paso que hay que hacer para ir de la idea de $O(n^3)$ a esta es decir "y si en vez de iterar en los bordes, itero en el centro?". Es preguntarse eso únicamente, que a veces que surja una pregunta así puede llevar mucho tiempo o incluso nunca surgirnos, y es la típica que cuando nos lo cuentan es "claaaaro cómo no lo vi". En mi opinión, estas ideas empiezan a surgir mientras vamos practicando; no hay una guía de "preguntas para hacerse en cualquier problema" que nos salva.


==== Algoritmo de Manacher - tiempo lineal ====

http://www.geeksforgeeks.org/manachers-algorithm-linear-time-longest-palindromic-substring-part-1/
OIA-Wiki

Herramientas de usuario

Herramientas del sitio

Herramientas de la página
