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

Question

我正在尝试解决一个问题，该问题要求在高达20,000个字符的字符串中找到最大的回文。我试图检查每个子字符串，无论它是一个腔杂志，都起作用，但显然太慢了。经过一番谷歌搜索，我发现了这种不错的算法http://stevekrenzel.com/articles/longest-palnidrome. 。我试图实施它，但是我无法正常工作。此外，给定的字符串包含非法字符，因此我必须将其转换为合法字符，并输出所有字符的最长的palindrome。

这是我的尝试：

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），一个用于奇数的palindrome长度，另一个用于偶数。
2. 该算法应仅在转换的字符串上执行。您必须首先将原始字符串转换为工作。

考虑此字符串： abc^ba （在哪里 ^ 是一个非法的角色），最长的回文不包括非法字符显然是 abcba, ，但是当你到达 i==2, ，然后将您的下部/上限移出一个，它们将定义 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个。一个用于均匀，一个用于旧的palindrom string。最后，我能够修复它。感谢您的建议。

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