5

我正在尝试解决一个问题，该问题要求在最多 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;
        }
    }
}

好的，所以我解决了问题，它工作得很好，但前提是转换字符串的长度是奇数。请帮忙。

4

3 回答 3

3

我可以看到两个主要错误：

  1. 是否将上/下指针初始化为 i,i 或 i,i+1 取决于您要查找的回文长度的奇偶性，而不是原始字符串。所以（没有任何进一步的优化）你需要两个单独的循环，i 从 0 到 len (len-1)，一个用于奇数回文长度，另一个用于偶数。
  2. 算法应仅在转换后的字符串上执行。您必须先转换原始字符串才能使其正常工作。

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

于 2011-03-14T21:01:14.427 回答
0 
#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 循环。一个用于偶数，一个用于旧回文字符串。最后我能够修复它。谢谢你的建议。

于 2012-10-20T13:14:11.187 回答
0 
 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;
    }
于 2019-04-07T06:00:08.203 回答