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

Question

Estoy tratando de resolver un problema que pide encontrar el palíndromo más grande en una cadena de hasta 20,000 caracteres. Traté de verificar cada subcadro si se trata de un palíndromo, que funcionó, pero obviamente fue demasiado lento. Después de un poco de Google encontré este bonito algoritmohttp://stevekrenzel.com/articles/longest-palnidrome. He tratado de implementarlo, sin embargo, no puedo hacer que funcione. Además, la cadena dada contiene caracteres ilegales, por lo que tengo que convertirlo a solo 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 hacer que funcione, he intentado usar este algoritmo exacto en papel y funcionó, por favor ayuda. Aquí hay código completo si lo necesita: http://pastebin.com/ssskr3gy

EDITAR:

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;
        }
    }
}

De acuerdo, solucioné los problemas, funciona perfectamente bien, pero solo si la longitud de la cadena convertida es extraña. Por favor ayuda.

Answer 1

Puedo ver dos errores principales:

1. Ya sea que inicie sus punteros superiores/inferiores para i, i o i, i+1 depende de la paridad de la longitud del palíndromo que desee encontrar, no de la cadena original. Entonces, (sin más optimizaciones) necesitará dos bucles separados con I yendo de 0 a Len (Len-1), uno para longitudes de palíndromo impares y otro para pares.
2. Los algoritmos deben ejecutarse solo en la cadena convertida. Tienes que convertir la cadena original primero para que funcione.

Considere esta cadena: abc^ba (dónde ^ es un personaje ilegal), el palíndromo más largo que excluye los personajes ilegales es claramente abcba, pero cuando llegas a i==2, y mover los límites inferiores/superiores por uno, definirán el bc^ subcadena, después de la conversión se convierte en bc, y b != c Entonces admites 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 ... usé 2 mientras que los bucles. uno para par y otro para la vieja cadena de palindrom. Finalmente pude arreglarlo. gracias por tu sugerencia.

Answer 3

 public void LongestPalindrome()
    {
        string str = "abbagdghhkjkjbbbbabaabbbbbba";

        StringBuilder str1=new StringBuilder();
        StringBuilder str2= new StringBuilder();

        for (int i = 0; i < str.Length; i++)
        {
            str1.Append((str[i]));
            for (int j = i + 1; j < str.Length; j++)
            {
                str1.Append((str[j]));
                if (Checkpalindrome(str1))
                {
                    str2.Append(str1);
                    str2.Append(" ");
                }
            }

            str1.Clear();
        }

        var Palstr = str2.ToString().Split(' ');
        var Longestpal = Palstr.Where(a => a.Length >= (Palstr.Max(y => y.Length)));
        foreach (var s in Longestpal)
        {
            Console.WriteLine(s);
        }
    }

    public bool Checkpalindrome(StringBuilder str)
    {
        string str1 = str.ToString();
        StringBuilder str2=new StringBuilder();
        var revstr = str1.Reverse();
        foreach (var c in revstr )
        {
            str2.Append(c);
        }

        if (str1.Equals(str2.ToString()))
        {
            return true;
        }

        return false;
    }