Trouver le plus grand palindrome dans la mise en œuvre de chaîne

Question

Je suis en train de résoudre un problème qui demande de trouver le plus grand palindrome dans une chaîne jusqu'à 20.000 caractères. J'ai essayé de vérifier chaque sous-chaîne, que ce soit un palindrome, qui a fonctionné, mais de toute évidence était trop lent. Après un peu googler j'ai trouvé ce bel algorithme http://stevekrenzel.com/articles/longest-palnidrome . J'ai essayé de le mettre en œuvre, mais je ne peux pas le faire fonctionner. Aussi la chaîne donnée contient des caractères illégaux, donc je dois le convertir en caractères seulement légaux et sortie la plus longue palindrome avec tous les caractères.

Voici ma tentative:

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


    }
}

Je ne peux pas le faire au travail, je l'ai essayé d'utiliser cet algorithme exact sur le papier et cela a fonctionné, aide s'il vous plaît. Voici le code complet si vous en avez besoin: 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;
        }
    }
}

Bon alors je fixe les problèmes, cela fonctionne parfaitement bien, mais seulement si la longueur de chaîne convertie est impair. S'il vous plaît aider.

Answer 1

Je vois deux erreurs majeures:

1. Que vous vos pointeurs initialise haut / bas pour i, i ou i, i + 1 dépend de la parité de la longueur du palindrome que vous voulez trouver, et non pas la chaîne d'origine. Donc, (sans autre Optimisations) vous aurez besoin de deux boucles distinctes avec i allant de 0 à len (len-1), une pour les longueurs de palindrome impaires et un autre pour même.
2. Les algorithmes doivent être exécutés sur la seule chaîne convertie. Vous devez convertir la chaîne d'origine première pour que cela fonctionne.

Considérez cette chaîne: abc^ba (où ^ est un caractère illégal), la plus longue palindrome exclusion des caractères illégaux est clairement abcba, mais quand vous arrivez à i==2, et déplacez vos bornes inférieures / supérieures par un, ils définiront le bc^ substring, après la conversion, il devient bc, et b != c donc vous admettez cette palindrome ne peut pas être étendu.

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: Comme vous l'avez dit .. i utilisé 2 ou while. un pour même et une pour la vieille chaîne de palindrome. enfin j'ai pu le réparer. Merci pour votre suggestion.

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