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

Question

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

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

我发现 this，并且有一个指向 O(n) 答案的链接，但它是用 Haskell 编写的，我不清楚。

如果能得到 c# 或类似的答案那就太好了。

Answer 1

我找到了解决方案的明确解释 此处。感谢贾斯汀提供此链接。

在那里您可以找到该算法的 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;
    }

Answer 2

这是它的 java 版本：

public static int LongestPalindrome(String seq) {
    int Longest = 0;
    List<Integer> l = new ArrayList<Integer>();
    int i = 0;
    int palLen = 0;
    int s = 0;
    int e = 0;

    while (i < seq.length()) {
        if (i > palLen && seq.charAt(i - palLen - 1) == seq.charAt(i)) {
            palLen += 2;
            i += 1;
            continue;
        }
        l.add(palLen);
        Longest = Math.max(Longest, palLen);
        s = l.size() - 2;
        e = s - palLen;
        boolean found = false;
        for (int j = s; j > e; j--) {
            int d = j - e - 1;
            if (l.get(j) == d) {
                palLen = d;
                found = true;
                break;
            }
            l.add(Math.min(d, l.get(j)));
        }
        if (!found) {
            palLen = 1;
            i += 1;
        }
    }
    l.add(palLen);
    Longest = Math.max(Longest, palLen);
    return Longest;
}

Answer 3

public static string GetMaxPalindromeString(string testingString)
{
    int stringLength = testingString.Length;
    int maxPalindromeStringLength = 0;
    int maxPalindromeStringStartIndex = 0;

    for (int i = 0; i < stringLength; i++)
    {
        int currentCharIndex = i;

        for (int lastCharIndex = stringLength - 1; lastCharIndex > currentCharIndex; lastCharIndex--)
        {
            if (lastCharIndex - currentCharIndex + 1 < maxPalindromeStringLength)
            {
                break;
            }

            bool isPalindrome = true;

            if (testingString[currentCharIndex] != testingString[lastCharIndex])
            {
                continue;
            }
            else
            {
                int matchedCharIndexFromEnd = lastCharIndex - 1;

                for (int nextCharIndex = currentCharIndex + 1; nextCharIndex < matchedCharIndexFromEnd; nextCharIndex++)
                {
                    if (testingString[nextCharIndex] != testingString[matchedCharIndexFromEnd])
                    {
                        isPalindrome = false;
                        break;
                    }
                    matchedCharIndexFromEnd--;
                }
            }

            if (isPalindrome)
            {
                if (lastCharIndex + 1 - currentCharIndex > maxPalindromeStringLength)
                {
                    maxPalindromeStringStartIndex = currentCharIndex;
                    maxPalindromeStringLength = lastCharIndex + 1 - currentCharIndex;
                }
                break;
            }
        }
    }

    if(maxPalindromeStringLength>0)
    {
        return testingString.Substring(maxPalindromeStringStartIndex, maxPalindromeStringLength);
    }

    return null;

}

Answer 4

C#

首先，我搜索偶数长度的回文。然后我搜索奇数长度的回文。当它找到回文时，它会确定长度并相应地设置最大长度。平均情况复杂度是线性的。

        protected static int LongestPalindrome(string str)
    {
        int i = 0; 
        int j = 1;
        int oldJ = 1;
        int intMax = 1;
        int intCount = 0;

        if (str.Length == 0) return 0;
        if (str.Length == 1) return 1;

        int[] intDistance = new int[2] {0,1};

        for( int k = 0; k < intDistance.Length; k++ ){

            j = 1 + intDistance[k];
            oldJ = j;
            intCount = 0;
            i = 0;

            while (j < str.Length)
            {


                if (str[i].Equals(str[j]))
                {
                    oldJ = j;
                    intCount = 2 + intDistance[k];
                    i--;
                    j++;
                    while (i >= 0 && j < str.Length)
                    {
                        if (str[i].Equals(str[j]))
                        {
                            intCount += 2;
                            i--;
                            j++;
                            continue;
                        }
                        else
                        {
                            break;
                        }

                    }
                    intMax = getMax(intMax, intCount);
                    j = oldJ + 1;
                    i = j - 1 - intDistance[k];

                }
                else
                {
                    i++;
                    j++;
                }
            }
        }

        return intMax;
    }

    protected static int getMax(int a, int b)
    {
        if (a > b) return a; return b;
    }

Answer 5

最近我在面试时写了以下代码......

    public string FindMaxLengthPalindrome(string s)
    {
        string maxLengthPalindrome = "";

        if (s == null) return s;

        int len = s.Length;

        for(int i = 0; i < len; i++)
        {
            for (int j = 0; j < len - i; j++)
            {
                bool found = true;
                for (int k = j; k < (len - j) / 2; k++)
                {
                    if (s[k] != s[len - (k - j + 1)])
                    {
                        found = false;
                        break;
                    }
                }

                if (found)
                {
                    if (len - j > maxLengthPalindrome.Length)
                        maxLengthPalindrome = s.Substring(j, len - j); 
                }

                if(maxLengthPalindrome.Length >= (len - (i + j)))
                    break;
            }

            if (maxLengthPalindrome.Length >= (len - i))
                break;
        }

        return maxLengthPalindrome;
    }

Answer 6

我在接受采访的时候就被问到了这个问题。

不幸的是，当我回到家时我才发现。

public static string GetMaxPalindromeString(string testingString)
    {
        int stringLength = testingString.Length;
        int maxPalindromeStringLength = 0;
        int maxPalindromeStringStartIndex = 0;

        for (int i = 0; i < testingString.Length; i++)
        {
            int currentCharIndex = i;

            for (int lastCharIndex = stringLength - 1; lastCharIndex > currentCharIndex; lastCharIndex--)
            {
                bool isPalindrome = true;

                if (testingString[currentCharIndex] != testingString[lastCharIndex])
                {
                    continue;
                }

                for (int nextCharIndex = currentCharIndex + 1; nextCharIndex < lastCharIndex / 2; nextCharIndex++)
                {
                    if (testingString[nextCharIndex] != testingString[lastCharIndex - 1])
                    {
                        isPalindrome = false;
                        break;
                    }
                }

                if (isPalindrome)
                {
                    if (lastCharIndex + 1 - currentCharIndex > maxPalindromeStringLength)
                    {
                        maxPalindromeStringStartIndex = currentCharIndex;
                        maxPalindromeStringLength = lastCharIndex + 1 - currentCharIndex;
                    }
                }
                break;
            }
        }

        return testingString.Substring(maxPalindromeStringStartIndex, maxPalindromeStringLength);
    }