在字符串实现中查找最大回文数

Question

在字符串实现中查找最大回文数

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

好的，我解决了问题，它完美地工作了，但仅当转换后的字符串长度为奇数时才有效。请帮忙。

- Marijus

1

也许这个问题应该发在 http://codereview.stackexchange.com/ 上？ - Pablo Venturino

3个回答

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

- Keertan Padmashali L

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：就像你说的一样，我使用了两个while循环，一个用于偶数，另一个用于旧回文字符串。最终我成功解决了问题。感谢你的建议。

- LOGAN

3

你应该总是对你提交的代码进行解释。 - alestanis

1

这段代码仅适用于长度为奇数的回文（例如“abcba”），而不适用于长度为偶数的回文（例如“abccba”）。 - Synxis

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- biziclop · Accepted Answer

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

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

考虑这个字符串：abc^ba（其中^是非法字符），最长的排除非法字符的回文串显然是abcba，但当你到达i==2时，并将你的下限/上限向外移动一个，它们将定义bc^子字符串，在转换后它变成了bc，并且b != c，所以你放弃了这个回文串可以被扩展。