如何找到最长的回文给定的字符串吗？ [英] How to find the longest palindrome in a given string?

问题描述

可能重复：
  <一href="http://stackoverflow.com/questions/1115001/write-a-function-that-returns-the-longest-palindrome-in-a-given-string">Write一个函数返回最长的回文中给定的字符串

我知道如何做到这一点的为O（n ^ 2）。但是好像存在一个更好的解决方案。

I know how to do this in O(n^2). But it seems like there exist a better solution.

我发现<一href="http://stackoverflow.com/questions/1115001/write-a-function-that-returns-the-longest-palindrome-in-a-given-string-e-g-ccdd">this,而且有一个链接到O（n）的答案，但它是写在Haskell并没有明确的对我。

I've found this, and there is a link to O(n) answer, but it's written in Haskell and not clear for me.

这将是伟大获得在C＃或类似的答案。

It would be great to get an answer in c# or similar.

推荐答案

我找到明确的解决方案，<一个解释href="http://www.akalin.cx/2007/11/28/finding-the-longest-palindromic-substring-in-linear-time/">here.感谢贾斯汀该链接。

I've found clear explanation of the solution here. Thanks to Justin for this link.

在那里，你可以找到的算法Python和Java的实现（C ++实现包含错误）。

There you can find Python and Java implementations of the algorithm (C++ implementation contains errors).

这里是C＃实现的是那些算法只是一个翻译。

And here is C# implementation that is just a translation of those algorithms.

public static int LongestPalindrome(string seq)
    {
        int Longest = 0;
        List<int> l = new List<int>();
        int i = 0;
        int palLen = 0;
        int s = 0;
        int e = 0;
        while (i<seq.Length)
        {
            if (i > palLen && seq[i-palLen-1] == seq[i])
            {
                palLen += 2;
                i += 1;
                continue;
            }
            l.Add(palLen);
            Longest = Math.Max(Longest, palLen);
            s = l.Count - 2;
            e = s - palLen;
            bool found = false;
            for (int j = s; j > e; j--)
            {
                int d = j - e - 1;
                if (l[j] == d)
                {
                    palLen = d;
                    found = true;
                    break;
                }
                l.Add(Math.Min(d, l[j]));
            }
            if (!found)
            {
                palLen = 1;
                i += 1;
            }
        }
        l.Add(palLen);
        Longest = Math.Max(Longest, palLen);
        return Longest;
    }

这篇关于如何找到最长的回文给定的字符串吗？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！