Нахождение самого большого палиндрома в строковой реализации

Question

Я пытаюсь решить проблему, которая просит найти самый большой палиндром в строке длиной до 20 000 символов.Я пытался проверить каждую подстроку, является ли это палиндромом, который работал, но, очевидно, был слишком медленным.После небольшого поиска в Google я нашел этот хороший алгоритм http://stevekrenzel.com/articles/longest-palnidrome. Я пытался реализовать его, однако я не могу заставить его работать.Также данная строка содержит недопустимые символы, поэтому я должен преобразовать ее в допустимые символы и вывести самый длинный палиндром со всеми символами.

Вот моя попытка:

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


    }
}

Я не могузаставить его работать, я попытался использовать этот точный алгоритм на бумаге, и это сработало, пожалуйста, помогите.Вот полный код, если вам это нужно: http://pastebin.com/sSskr3GY

РЕДАКТИРОВАТЬ:

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

Хорошо, так что я исправил проблемы, он работает отлично, но толькоесли длина преобразованной строки нечетна.Пожалуйста, помогите.

Answer 1

Я вижу две основные ошибки:

1. Инициализируете ли вы свои верхние / нижние указатели для i, i или i, i + 1, зависит от четности длины палиндрома, которую вы хотите найти, а не от исходной строки. Таким образом (без каких-либо дополнительных оптимизаций) вам понадобятся два отдельных цикла с i, переходящим от 0 к len (len-1), один для нечетной длины палиндрома и другой для четного.
2. Алгоритмы должны выполняться только для преобразованной строки. Вы должны сначала преобразовать исходную строку, чтобы она заработала.

Рассмотрим эту строку: abc^ba (где ^ - недопустимый символ), самый длинный палиндром, исключающий недопустимые символы, явно равен abcba, но когда вы доберетесь до i==2 и переместите нижнюю / верхнюю границы по одному они будут определять подстроку bc^, после преобразования она становится bc, и b != c, поэтому вы допускаете, что этот палиндром не может быть расширен.

Answer 2

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

Answer 3

#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: Как вы сказали ... я использовал 2 цикла while. один для четного и один для старой строки палиндром. наконец я смог это исправить. спасибо за ваше предложение.