编写一个函数，返回给定字符串中最长的回文字符串。

Question

例如，在字符串“abaccddccefe”中寻找“ccddcc”。

我想到了一种解法，但是它的时间复杂度为O(n^2)。

算法1: 步骤: 这是一种暴力方法 1. 有两个for循环 对于i = 1到i小于array.length-1 对于j=i+1到j小于array.length 2. 这样就可以从数组中获得每个可能组合的子串。 3. 拥有一个回文函数来检查一个字符串是否是回文的。 4. 因此，对于每个子串(i,j)，调用此函数，如果它是回文的，则将其存储在一个字符串变量中。 5. 如果你发现下一个回文子串大于当前子串，则用当前子串替换它。 6. 最后，您的字符串变量将具有答案。

问题： 1. 这个算法的时间复杂度为O(n^2)。

算法二： 1. 反转字符串并将其存储在不同的数组中 2. 现在在两个数组之间找到最大匹配的子字符串 3. 但这也需要O(n^2)的时间

你们能想出一个更好的算法吗？如果可能的话，请使用O(n)时间。

- Learner

---

我认为第一种方法需要O(n^2)的时间来获取所有子字符串，再需要O(n)的时间检查它们是否是回文，总共需要O(n^3)的时间复杂度？ - Skylar Saveland

如果我知道我正在处理回文，并将我的字符串保存为两半，那么如果我使用Java，我将拥有O(1)函数检查，对吗？ - viki.omega9

第二个算法正确吗？那么对于字符串："abcdecba"，最大的匹配子串是什么呢("abcdecba" vs. "abcedcba")? "abc" 或者 "cba"。然而，这两个都不是回文。 - Yarneo

@Learner，只是好奇，在你上面的步骤中，你在for循环中引用了哪个数组？你所指的数组是指字符串吗？string.length？ - Zolt

对于那些正在寻找O(n^2)答案的人，请参考以下链接：https://www.geeksforgeeks.org/longest-palindrome-substring-set-1/ - Shirish Herwade

Answer 1

你可以使用马拉车算法在O(n)的时间内找到最长回文子串！该算法的实现代码可以从这里和这里获取。

对于输入的字符串 s = "HYTBCABADEFGHABCDEDCBAGHTFYW1234567887654321ZWETYGDE"，该算法可以找到正确的输出结果 1234567887654321。

- Anuj Kulkarni

---

我不明白这怎么是线性的。我看到一个while嵌套在for中，边界似乎与外部循环相似。 - v.oddou

当有人访问Stack Overflow时，问题的“答案”应该实际包含一个回答，而不仅仅是一堆指向答案的方向。 - Erik Philips

Answer 2

Algo 2 可能不适用于所有字符串。以下是这样一个字符串的示例：“ABCDEFCBA”。

请注意，该字符串具有“ABC”和“CBA”作为它的子字符串。如果您反转原始字符串，它将变成“ABCFEDCBA”。最长匹配子字符串是“ABC”，它不是回文。

您可能需要额外检查这个最长匹配子字符串是否实际上是一个回文，这将耗费O(n^3)的时间。

- VCB

---

需要注意的是，Algo 2 应该适用于“最长匹配子序列回文”，这是一个常见的算法问题，其中子序列字符也可以在字符串内部分开。例如，上面两个字符串之间的最长匹配子序列（包括字符分隔符）是“ABCFCBA”，它也是一个回文 :) 这里有一个链接描述了 LCS 问题：http://www.ics.uci.edu/~eppstein/161/960229.html - Jake Drew

Answer 3

据我所了解，我们可以在中心索引周围找到回文并向两侧扩展搜索。考虑到输入的角落没有回文，因此我们可以将边界设置为1和长度-1。在注意字符串的最小和最大边界的同时，我们检查每个中心位置的对称索引（右和左）处的字符是否相同，直到达到我们的最大上限中心。

外循环是O(n)（最多n-2次迭代），内部while循环是O(n)（最多约(n / 2)-1次迭代）

这是我的Java实现，使用其他用户提供的示例。

class LongestPalindrome {

    /**
     * @param input is a String input
     * @return The longest palindrome found in the given input.
     */
    public static String getLongestPalindrome(final String input) {
        int rightIndex = 0, leftIndex = 0;
        String currentPalindrome = "", longestPalindrome = "";
        for (int centerIndex = 1; centerIndex < input.length() - 1; centerIndex++) {
            leftIndex = centerIndex - 1;  rightIndex = centerIndex + 1;
            while (leftIndex >= 0 && rightIndex < input.length()) {
                if (input.charAt(leftIndex) != input.charAt(rightIndex)) {
                    break;
                }
                currentPalindrome = input.substring(leftIndex, rightIndex + 1);
                longestPalindrome = currentPalindrome.length() > longestPalindrome.length() ? currentPalindrome : longestPalindrome;
                leftIndex--;  rightIndex++;
            }
        }
        return longestPalindrome;
    }

    public static void main(String ... args) {
        String str = "HYTBCABADEFGHABCDEDCBAGHTFYW12345678987654321ZWETYGDE";
        String longestPali = getLongestPalindrome(str);
        System.out.println("String: " + str);
        System.out.println("Longest Palindrome: " + longestPali);
    }
}

这个的输出结果如下：

marcello:datastructures marcello$ javac LongestPalindrome
marcello:datastructures marcello$ java LongestPalindrome
String: HYTBCABADEFGHABCDEDCBAGHTFYW12345678987654321ZWETYGDE
Longest Palindrome: 12345678987654321

- Marcello DeSales

---

如果我给出“HYTBCABADEFGHABCDEDCBAGHTFYW1234567887654321ZWETYGDE”，它不起作用，但答案应该是1234567887654321。 - Elbek

@j_random_hacker 不是的，那是二次方程的解之一。这在这里中有详细介绍，称为“expandAroundCenter”。 - v.oddou

@v.oddou：你说得完全正确，我不知道怎么会得出O(n^3)，因为只有两个嵌套循环！我会删除那个错误的评论...但我也注意到这个解决方案有一个问题，我会在另一个评论中提出，希望作者能够注意到。 - j_random_hacker

我之前对O（n ^ 3）时间复杂度的说法是错误的（感谢@v.oddou指出！），但还有另一个问题：这段代码没有考虑长度为偶数的回文串。 这可以通过添加第二个非常相似的外部循环来修复（也是O（n ^ 2），因此不会影响O（n ^ 2）时间复杂度），该循环在每对字符之间的n-1个位置中扩展回文。如果您进行修正，将得到+2 :) - j_random_hacker

Answer 4

我出于好奇写了下面这个Java程序，它简单易懂。希望对你有所帮助，谢谢。

/**
 *
 * @author sanhn
 */
public class CheckPalindrome {

    private static String max_string = "";

    public static void checkSubString(String s){
        System.out.println("Got string is "+s);
        for(int i=1;i<=s.length();i++){
            StringBuilder s1 = new StringBuilder(s.substring(0,i));
            StringBuilder s2 = new StringBuilder(s.substring(0,i));
            s2.reverse();
            if(s1.toString().equals(s2.toString())){
                if(max_string.length()<=s1.length()){
                    max_string = s1.toString();
                    System.out.println("tmp max is "+max_string);
                }

            }
        }
    }

    public static void main(String[] args){
        String s="HYTBCABADEFGHABCDEDCBAGHTFYW1234567887654321ZWETYGDE";

        for(int i=0; i<s.length(); i++)
            checkSubString(s.substring(i, s.length()));

        System.out.println("Max string is "+max_string);
    }
}

- Cleonjoys

Answer 5

您好，以下是寻找字符串中最长回文的代码。

请参考以下链接了解算法：http://stevekrenzel.com/articles/longest-palnidrome

使用的测试数据为HYTBCABADEFGHABCDEDCBAGHTFYW12345678987654321ZWETYGDE

 //Function GetPalindromeString

public static string GetPalindromeString(string theInputString)
 { 

        int j = 0;
        int k = 0;
        string aPalindrome = string.Empty;
        string aLongestPalindrome = string.Empty ;          
        for (int i = 1; i < theInputString.Length; i++)
        {
            k = i + 1;
            j = i - 1;
            while (j >= 0 && k < theInputString.Length)
            {
                if (theInputString[j] != theInputString[k])
                {
                    break;
                }
                else
                {
                    j--;
                    k++;
                }
                aPalindrome = theInputString.Substring(j + 1, k - j - 1);
                if (aPalindrome.Length > aLongestPalindrome.Length)
                {
                    aLongestPalindrome = aPalindrome;
                }
            }
        }
        return aLongestPalindrome;     
  }

- Mohit Bhandari

---

我不确定这是否适用于偶数长度的回文……你能确认一下吗？ - st0le

这适用于偶数回文，您可以运行此程序并让我知道是否对您不起作用。如需了解算法，请参阅以下链接http://stevekrenzel.com/articles/longest-palnidrome - Mohit Bhandari

@st0le：这个逻辑对于偶数回文数不起作用，但可以调整为适用于偶数回文数。请原谅我之前的评论。我已经理解了这个逻辑，并且在有时间的时候会在几天内更新它。 - Mohit Bhandari

直到今天我才看到你的评论...上次你没有回复我...不着急，这只是一种观察。 - st0le

我最初认为OP的算法#1是O(n^2)时间复杂度，但实际上它是愚蠢的O(n^3)，所以即使你的算法没有达到可实现的O(n)上限，它仍然是一种改进。 - j_random_hacker

Answer 6

使用正则表达式和Ruby，您可以像这样扫描短回文：

PROMPT> irb
>> s = "longtextwithranynarpalindrome"
=> "longtextwithranynarpalindrome"
>> s =~ /((\w)(\w)(\w)(\w)(\w)\6\5\4\3\2)/; p $1
nil
=> nil
>> s =~ /((\w)(\w)(\w)(\w)\w\5\4\3\2)/; p $1
nil
=> nil
>> s =~ /((\w)(\w)(\w)(\w)\5\4\3\2)/; p $1
nil
=> nil
>> s =~ /((\w)(\w)(\w)\w\4\3\2)/; p $1
"ranynar"
=> nil

- neoneye

Answer 7

public static void main(String[] args) {
         System.out.println(longestPalindromeString("9912333321456")); 
}

    static public String intermediatePalindrome(String s, int left, int right) {
        if (left > right) return null;
        while (left >= 0 && right < s.length()
                && s.charAt(left) == s.charAt(right)) {
            left--;
            right++;
        }
        return s.substring(left + 1, right);
    }


    public static String longestPalindromeString(String s) {
        if (s == null) return null;
        String longest = s.substring(0, 1);
        for (int i = 0; i < s.length() - 1; i++) {
            //odd cases like 121
            String palindrome = intermediatePalindrome(s, i, i);
            if (palindrome.length() > longest.length()) {
                longest = palindrome;
            }
            //even cases like 1221
            palindrome = intermediatePalindrome(s, i, i + 1);
            if (palindrome.length() > longest.length()) {
                longest = palindrome;
            }
        }
        return longest;
    }

- Sushil Mittal

Answer 8

最近有人问了我这个问题。这是我最终想出的解决方案。我用JavaScript实现，因为在这种语言中非常简单明了。

基本概念是你遍历字符串，寻找可能的最小多字符回文（两个或三个字符）。一旦找到，就向两侧扩展边界，直到不再是回文为止。如果长度比当前最长的回文还要长，就存储它并继续寻找。

// This does the expanding bit.
function getsize(s, start, end) {
    var count = 0, i, j;
    for (i = start, j = end; i >= 0 && j < s.length; i--, j++) {
        if (s[i] !== s[j]) {
            return count;
        }
        count = j - i + 1; // keeps track of how big the palindrome is
    }
    return count;
}

function getBiggestPalindrome(s) {
    // test for simple cases
    if (s === null || s === '') { return 0; }
    if (s.length === 1) { return 1; }
    var longest = 1;
    for (var i = 0; i < s.length - 1; i++) {
        var c = s[i]; // the current letter
        var l; // length of the palindrome
        if (s[i] === s[i+1]) { // this is a 2 letter palindrome
            l = getsize(s, i, i+1);
        }
        if (i+2 < s.length && s[i] === s[i+2]) { // 3 letter palindrome
            l = getsize(s, i+1, i+1);
        }
        if (l > longest) { longest = l; }
    }
    return longest;
}

这段代码可以进一步优化和清理，但在除了最坏情况（一串相同字母）以外的情况下，它应该具有相当不错的性能。

- swilliams

---

我最初认为OP的算法#1是O(n^2)时间复杂度，但实际上它是愚蠢的O(n^3)，所以即使你的算法没有达到可实现的O(n)上限，它仍然是一种改进。 - j_random_hacker

你称这个为“直截了当”，但它充满了 i j l s if 和状态维护。有多个返回点，边缘情况... - v.oddou

Answer 9

一种高效的Regexp解决方案，避免了暴力破解

从整个字符串长度开始向下工作到2个字符，一旦匹配成功就存在

对于"abaccddccefe"，正则表达式在返回ccddcc之前测试了7个匹配项。

(.)(.)(.)(.)(.)(.)(\6)(\5)(\4)(\3)(\2)(\1)
(.)(.)(.)(.)(.)(.)(\5)(\4)(\3)(\2)(\1)
(.)(.)(.)(.)(.)(\5)(\4)(\3)(\2)(\1)
(.)(.)(.)(.)(.)(\4)(\3)(\2)(\1)
(.)(.)(.)(.)(\4)(\3)(\2)(\1)
(.)(.)(.)(.)(\3)(\2)(\1)
(.)(.)(.)(\3)(\2)(\1)

vbs

translates to

{{链接1:vbs}}

in Chinese.

Dim strTest
wscript.echo Palindrome("abaccddccefe")

vba

Sub Test()
Dim strTest
MsgBox Palindrome("abaccddccefe")
End Sub

函数

Function Palindrome(strIn)

Set objRegex = CreateObject("vbscript.regexp")

For lngCnt1 = Len(strIn) To 2 Step -1
    lngCnt = lngCnt1 \ 2
    strPal = vbNullString

    For lngCnt2 = lngCnt To 1 Step -1
        strPal = strPal & "(\" & lngCnt2 & ")"
    Next

    If lngCnt1 Mod 2 = 1 Then strPal = "(.)" & strPal

    With objRegex
        .Pattern = Replace(Space(lngCnt), Chr(32), "(.)") & strPal
        If .Test(strIn) Then
            Palindrome = .Execute(strIn)(0)
            Exit For
        End If
    End With
Next

End Function

- brettdj

---

@DickKusleika 能否请您使用上面的修订代码更新我的评论，链接为http://dailydoseofexcel.com/archives/2016/01/14/anagrams-and-palindromes/#comments。谢谢。 - brettdj

Answer 10

请见本主题的维基百科文章。下面的文章提供了Manacher算法Java实现的示例，可实现线性O(n)解决方案：

import java.util.Arrays; public class ManachersAlgorithm { public static String findLongestPalindrome(String s) { if (s==null || s.length()==0) return "";

char[] s2 = addBoundaries(s.toCharArray());
int[] p = new int[s2.length]; 
int c = 0, r = 0; // Here the first element in s2 has been processed.
int m = 0, n = 0; // The walking indices to compare if two elements are the same
for (int i = 1; i<s2.length; i++) {
  if (i>r) {
    p[i] = 0; m = i-1; n = i+1;
  } else {
    int i2 = c*2-i;
    if (p[i2]<(r-i)) {
      p[i] = p[i2];
      m = -1; // This signals bypassing the while loop below. 
    } else {
      p[i] = r-i;
      n = r+1; m = i*2-n;
    }
  }
  while (m>=0 && n<s2.length && s2[m]==s2[n]) {
    p[i]++; m--; n++;
  }
  if ((i+p[i])>r) {
    c = i; r = i+p[i];
  }
}
int len = 0; c = 0;
for (int i = 1; i<s2.length; i++) {
  if (len<p[i]) {
    len = p[i]; c = i;
  }
}
char[] ss = Arrays.copyOfRange(s2, c-len, c+len+1);
return String.valueOf(removeBoundaries(ss));   }
private static char[] addBoundaries(char[] cs) {
if (cs==null || cs.length==0)
  return "||".toCharArray();

char[] cs2 = new char[cs.length*2+1];
for (int i = 0; i<(cs2.length-1); i = i+2) {
  cs2[i] = '|';
  cs2[i+1] = cs[i/2];
}
cs2[cs2.length-1] = '|';
return cs2;   }
private static char[] removeBoundaries(char[] cs) {
if (cs==null || cs.length<3)
  return "".toCharArray();

char[] cs2 = new char[(cs.length-1)/2];
for (int i = 0; i<cs2.length; i++) {
  cs2[i] = cs[i*2+1];
}
return cs2;   }     }

- Datageek