在字符串实现中找到最大的回文

Question

我正在尝试解决一个问题，要求在一个字符串中找到最多20,000个字符的最大回文。我试图检查每个子字符串是否是回文，这是有效的，但显然太慢了。经过一番谷歌搜索后，我发现了这个很好的算法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取决于你想要找到的回文长度的奇偶性，而不是原始字符串。所以（没有任何进一步的优化）你将需要两个单独的循环，我从0到len（len-1），一个用于奇数回文长度，另一个用于偶数。
2. 算法应仅在转换后的字符串上执行。您必须首先转换原始字符串才能工作。

考虑这个字符串：abc^ba（其中^是非法字符），排除非法字符的最长回文明显是abcba，但是当你到达i==2，并将你的下限/上限移出1时，他们将定义bc^子字符串，之后转换它变成bc，和b != c所以你承认这个回文不能延长。

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：正如你所说..我使用了2个循环。一个用于偶数，一个用于旧的回文串。最后我能够解决它。谢谢你的建议。

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