Encontrar el palíndromo más grande en la implementación de cadenas

Question

Estoy tratando de resolver un problema que requiere encontrar el palíndromo más grande en una cadena de hasta 20,000 caracteres. He intentado comprobar cada subcadena, ya sea un palíndromo, que funcionó, pero obviamente fue demasiado lento. Después de un poco de google encontré este buen algoritmo http://stevekrenzel.com/articles/longest-palnidrome. Intenté implementarlo, pero no puedo hacerlo funcionar. Además, la cadena dada contiene caracteres ilegales, por lo que debo convertirla solo en caracteres legales y generar el palíndromo más largo con todos los caracteres.

Aquí está mi intento:

int len = original.length(); 
int longest = 0; 
string answer; 

for (int i = 0; i < len-1; i++){ 

    int lower(0), upper(0); 

    if (len % 2 == 0){ 
     lower = i; 
     upper = i+1; 
    } else { 
     lower = i; 
     upper = i; 
    } 

    while (lower >= 0 && upper <= len){ 
     string s2 = original.substr(lower,upper-lower+1); 
     string s = convert(s2); 

     if (s[0] == s[s.length()-1]){ 
      lower -= 1; 
      upper += 1; 
     } else { 
      if (s.length() > longest){ 
       longest = s.length(); 
       answer = s2; 
      } 
      break; 
     } 


    } 
} 

no puedo conseguir que funcione, lo he intentado usar este algoritmo exacto en el papel y funcionó, por favor ayuda. Aquí está el código completo, si lo necesita: http://pastebin.com/sSskr3GY

EDIT:

int longest = 0; 
string answer; 
string converted = convert(original); 
int len = converted.length(); 

if (len % 2 == 0){ 
    for (int i = 0; i < len - 1; i++){ 
     int lower(i),upper(i+1); 
     while (lower >= 0 && upper <= len && converted[lower] == converted[upper]){ 
      lower -= 1; 
      upper += 1; 
     } 
     string s = converted.substr(lower+1,upper-lower-1); 
     if (s.length() > longest){ 
      longest = s.length(); 
      answer = s; 
     } 
    } 
} else { 
    for (int i = 0; i < len; i++){ 
     int lower(i), upper(i); 
     while (lower >= 0 && upper <= len && converted[lower] == converted[upper]){ 
      lower -= 1; 
      upper += 1; 
     } 
     string s = converted.substr(lower+1,upper-lower-1); 
     if (s.length() > longest){ 
      longest = s.length(); 
      answer = s; 
     } 
    } 
} 

Bueno por lo que han solucionado los problemas, funciona perfectamente bien, pero sólo si la longitud de la cadena convertida es impar. Por favor ayuda.

Answer 1

puedo ver dos grandes errores:

1. Tanto si inicializar punteros superior/inferior a i, i o i, i + 1 depende de la paridad de la longitud del palíndromo que desea buscar, no el cuerda original Entonces (sin más optimizaciones) necesitarás dos bucles separados yendo de 0 a len (len-1), uno para longitudes de palindrome impares y otro para par.
2. Los algoritmos solo se deben ejecutar en la cadena convertida. Primero debe convertir la cadena original para que funcione.

Considere esta cadena: abc^ba (donde ^ un carácter no válido), el palíndromo más largo sin caracteres ilegales es claramente abcba, pero cuando se llega a i==2, y mover los límites inferiores/superiores a cabo por uno, van a defina la subcadena bc^, después de la conversión se convierte en bc y b != c, por lo que admite que este palíndromo no se puede extender.

Answer 2

#include <iostream> 
using namespace std; 

int main() 
{ 

string s; 
cin >> s; 
signed int i=1; 
signed int k=0; 
int ml=0; 
int mi=0; 
bool f=0; 

while(i<s.length()) 
{ 
    if(s[i]!=s[i+1]) 
    { 
     for(k=1;;k++) 
      { 
       if(!(s[i-k]==s[i+k] && (i-k)>=0 && (i+k)<s.length())) 
       {    
        break; 
       } 
      else if(ml < k) 
       { 
        ml=k; 
        mi=i; 
        f=1; 
       } 
      } 
    } 
i++; 
} 

i=0; 

while(i<s.length()) 
{ 
    if(s[i]==s[i+1]) 
    { 
     for(k=1;;k++) 
     { 
       if(!(s[i-k]==s[k+1+i] && (i-k)>=0 && (k+i)<s.length())) 
       { 
        break; 
       } 
       else if(ml < k) 
       { 
       ml=k; 
        mi=i; 
       } 
      }      
    } 
    i++; 
} 

if(ml < 1) 
{ 
    cout << "No Planidrom found"; 
    return 0; 
} 

if(f==0) 
{ 
cout << s.substr(mi-ml,2*ml+2); 
} 
else 
{ 
cout << s.substr(mi-ml,2*ml+1); 
} 

return 0; 

} 

@biziclop: Como dijiste .. utilicé 2 while loops. uno para pares y uno para cuerdas viejas de palindrom. finalmente pude arreglarlo. gracias por tu sugerencia.