如何找到给定字符串中最长的回文？

Question

可能重复:
编写一个返回给定字符串中最长回文的函数

我知道如何在O(n ^ 2)中做到这一点.但似乎存在更好的解决方案.

我发现了这个,并且有一个O(n)答案的链接,但它是用Haskell编写的,对我来说并不清楚.

在c#或类似的答案中获得答案会很棒.

Answer 1

我已经找到了解决方案的明确解释这里.感谢Justin的链接.

在那里你可以找到算法的Python和Java实现(C++实现包含错误).

这里是C#实现,它只是这些算法的翻译.

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