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

Question

例如字符串“abaccddccefe”中的“ccddcc”

我想到了一个解决方案，但它运行时间为O(n^2)

算法1：

步骤： 这是一种蛮力方法

1. 有 2 个 for 循环
   对于 i = 1 到 i 小于 array.length -1
   对于 j=i+1 到 j 小于 array.length 通过
2. 这种方式，您可以从数组中获取每个可能组合的子字符串
3. 有一个回文函数，用于检查字符串是否为回文，
4. 因此对于每个子字符串 (i,j) 调用此函数，如果它是回文，则将其存储在字符串变量中。
5. 如果找到下一个回文子串，并且它大于当前的子串，则将其替换为当前的回文子串。
6. 最后你的字符串变量将有

问题的答案： 1. 该算法运行时间为 O(n^2)。

算法 2：

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

你们能想到一个运行时间更好的算法吗？ 如果可能的话 O(n) 时间

Answer 1

您可以使用 Manacher 算法 在 O(n)时间！ 它的实现可以在此处和此处。

对于输入String s = "HYTBCABADEFGHABCDEDCBAGHTFYW1234567887654321ZWETYGDE"，它会找到正确的输出，即1234567887654321。

Answer 2

Algo 2 可能不适用于所有字符串。 以下是此类字符串“ABCDEFCBA”的示例。

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

您可能还需要额外检查这个最长匹配子串是否实际上是一个运行时间为 O(n^3) 的回文。

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

Answer 4

使用正则表达式和 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

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

Answer 6

出于好奇、简单且不言自明的 HTH，我编写了以下 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);
    }
}

Answer 7

最近有人问我这个问题。 这是我[最终]想出的解决方案。 我用 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;
}

这肯定可以进一步清理和优化，但除了最坏的情况（同一字母的字符串）之外，它在所有情况下都应该具有相当好的性能。

Answer 8

请参阅有关此主题的维基百科文章。 线性 O(n) 的 Manacher 算法 Java 实现示例解决方案来自下面的文章：

导入java.util.Arrays； 公共类 ManachersAlgorithm {
公共静态字符串findLongestPalindrome（字符串s）{
if (s==null || s.length()==0)
返回“”；

char[] s2 = addBoundaries(s.toCharArray()); 
  int[] p = new int[s2.length];  
  int c = 0，r = 0；   // 此处 s2 中的第一个元素已被处理。 
  整数 m = 0，n = 0；   // 比较两个元素是否相同的步行索引 
  for (int i = 1; ir）{ 
      p[i] = 0；   m = i-1;   n = i+1； 
    } 别的 { 
      int i2 = c*2-i; 
      if (p[i2]<(ri)) { 
        p[i] = p[i2]; 
        米=-1；   // 这表示绕过下面的 while 循环。  
      } 别的 { 
        p[i] = ri； 
        n = r+1；   m = i*2-n； 
      } 
    } 
    while (m>=0 && nr) { 
      c = 我；   r = i+p[i]; 
    } 
  } 
  int 长度 = 0;   c = 0; 
  for (int i = 1; i




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

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

Answer 10

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

Answer 11

尝试字符串 -“HYTBCABADEFGHABCDEDCBAGHTFYW123456789987654321ZWETYGDE”；
它应该适用于偶数和奇数朋友。 非常感谢莫希特！

使用命名空间 std；

string largestPal(string input_str)
{
  string isPal = "";
  string largest = "";
  int j, k;
  for(int i = 0; i < input_str.length() - 1; ++i)
    {
      k = i + 1;
      j = i - 1;

      // starting a new interation                                                      
      // check to see if even pal                                                       
      if(j >= 0 && k < input_str.length()) {
        if(input_str[i] == input_str[j])
          j--;
        else if(input_str[i] == input_str[j]) {
          k++;
        }
      }
      while(j >= 0 && k < input_str.length())
        {
          if(input_str[j] != input_str[k])
            break;
          else
            {
              j--;
              k++;
            }
          isPal = input_str.substr(j + 1, k - j - 1);
            if(isPal.length() > largest.length()) {
              largest = isPal;
            }
        }
    }
  return largest;
}

Answer 12

以下代码计算偶数长度和奇数长度字符串的 Palidrom。

不是最好的解决方案，但适用于两种情况

HYTBCABADEFGHABCDEDCBAGHTFYW12345678987654321ZWETYGDE
HYTBCABADEFGHABCDEDCBAGHTFYW1234567887654321ZWETYGDE

private static String getLongestPalindrome(String string) {
    String odd = getLongestPalindromeOdd(string);
    String even = getLongestPalindromeEven(string);
    return (odd.length() > even.length() ? odd : even);
}

public static String getLongestPalindromeOdd(final String input) {
    int rightIndex = 0, leftIndex = 0;
    String currentPalindrome = "", longestPalindrome = "";
    for (int centerIndex = 1; centerIndex < input.length() - 1; centerIndex++) {
        leftIndex = centerIndex;
        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 String getLongestPalindromeEven(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;
}

Answer 13

1. 修改字符串，使用分隔符分隔每个字符[这是为了合并奇数和偶数回文]
2. 以每个字符为中心查找回文

我们可以使用它找到所有长度的所有回文。

示例：

word = abcdcbc

moddedString = a#b#c#d#c#b#c

palinCount = 1010105010301

最长回文长度 = 5；

最长回文 = bcdcb

public class MyLongestPalindrome {

static String word;
static int wordlength;
static int highestcount = 0;
static int newlength;
static char[] modifiedString; // stores modified string
static int[] palinCount; // stores palindrome length at each position
static char pound = '#';

public static void main(String[] args) throws IOException {
    // TODO Auto-generated method stub
    System.out.println("Enter String : ");
    InputStreamReader isr = new InputStreamReader(System.in);
    BufferedReader bfr = new BufferedReader(isr);
    word = bfr.readLine();
    wordlength = word.length();
    newlength = (wordlength * 2) - 1;
    convert();
    findpalindrome();
    display();
}

// Inserting # in string
public static void convert() {

    modifiedString = new char[newlength];
    int j = 0;
    int i;
    for (i = 0; i < wordlength - 1; i++) {
        modifiedString[j++] = word.charAt(i);
        modifiedString[j++] = pound;
    }
    modifiedString[j] = word.charAt(i);
}

// display all palindromes of highest length
public static void display() {
    String palindrome;
    String s = new String(modifiedString);
    System.out.println("Length of longest palindrome = " + highestcount);
    for (int i = 0; i < newlength; i++) {
        if (palinCount[i] == highestcount) {
            palindrome = s.substring(i - (highestcount - 1), i
                    + (highestcount));
            i = i + (highestcount - 1);
            palindrome = palindrome.replace("#", "");
            System.out.println(palindrome);
        }
    }
}

// populate palinCount with length of palindrome string at each position
public static void findpalindrome() {
    int left, right, count;
    palinCount = new int[newlength];
    palinCount[0] = 1;
    palinCount[newlength - 1] = 1;
    for (int i = 1; i < newlength - 1; i++) {
        count = 0;
        left = i - 1;
        right = i + 1;
        ;
        if (modifiedString[i] != pound)
            count++;
        while (left >= 0 && right < newlength) {
            if (modifiedString[left] == modifiedString[right]) {
                if (modifiedString[left] != pound)
                    count = count + 2;
                left--;
                right++;
            } else
                break;
        }

        palinCount[i] = count;
        highestcount = count > highestcount ? count : highestcount;

    }

}

}

Answer 14

这将从给定字符串返回最长的回文字符串

-(BOOL)isPalindromString:(NSString *)strInput
{
    if(strInput.length<=1){
        return NO;
    }
    int halfLenth = (int)strInput.length/2;

    BOOL isPalindrom = YES;
    for(NSInteger i=0; i<halfLenth; i++){

        char a = [strInput characterAtIndex:i];
        char b = [strInput characterAtIndex:(strInput.length-1)-i];

        if(a != b){
            isPalindrom = NO;
            break;
        }
    }
    NSLog(@"-%@- IS Plaindrom %@",strInput,(isPalindrom ? @"YES" : @"NO"));
    return isPalindrom;
}


-(NSString *)longestPalindrom:(NSString *)strInput
{
    if(strInput.length<=1){
        return @"";
    }

    NSString *strMaxPalindrom = @"";

    for(int i = 0; i<strInput.length ; i++){

        for(int j = i; j<strInput.length ; j++){

            NSString *strSub = [strInput substringWithRange:NSMakeRange(i, strInput.length-j)];

            if([self isPalindromString:strSub]){

                if(strSub.length>strMaxPalindrom.length){

                    strMaxPalindrom = strSub;
                }
            }
        }
    }
    NSLog(@"-Max - %@",strMaxPalindrom);
    return strMaxPalindrom;
}

-(void)test
{
    [self longestPalindrom:@"abcccbadeed"];
}

== 输出 ===

输入：abcccde 输出：ccc

输入：abcccbd 输出：bcccb

输入：abedccde 输出：edccde

输入：abcccdeed 输出：deed

输入：abcccbadeed 输出：abcccba

Answer 15

这是 JavaScript 中的一个实现：

var longestPalindromeLength = 0;
var longestPalindrome = ''

function isThisAPalidrome(word){
  var reverse = word.split('').reverse().join('')
  return word == reverse
}

function findTheLongest(word){ // takes a word of your choice
  for(var i = 0; i < word.length; i++){ // iterates over each character
    var wordMinusOneFromBeginning = word.substr(i, word.length) // for each letter, create the word minus the first char
    for(var j = wordMinusOneFromBeginning.length; j > 0; j--){ // for the length of the word minus the first char
      var wordMinusOneFromEnding = wordMinusOneFromBeginning.substr(0, j) // create a word minus the end character
      if(wordMinusOneFromEnding <= 0) // make sure the value is more that 0,
      continue // if more than zero, proced to next if statement
      if(isThisAPalidrome(wordMinusOneFromEnding)){ // check if the word minus the first character, minus the last character = a plaindorme
        if(wordMinusOneFromEnding.length > longestPalindromeLength){ // if it is
          longestPalindromeLength = wordMinusOneFromEnding.length; // save its length
          longestPalindrome = wordMinusOneFromEnding // and save the string itself
        } // exit the statement that updates the longest palidrome
      } // exit the stament that checks for a palidrome
    } // exit the loop that goes backwards and takes a letter off the ending
  } // exit the loop that goes forward and takes off the beginning letter
  return console.log('heres the longest string: ' + longestPalindrome
  + ' its ' + longestPalindromeLength + ' charachters in length'); // return the longest palidrome! :)
}
findTheLongest('bananas');

Answer 16

对于线性求解，可以使用 Manacher 算法。 还有另一种算法称为 Gusfield 算法，下面是 java 中的代码：

public class Solution {  
    char[] temp;   
    public int match(int a, int b,int len){   
        int i = 0;   
        while (a-i>=0 && b+i<len && temp[a-i] == temp[b+i]) i++;   
        return i;   
    }  

    public String longestPalindrome(String s) {  

        //This makes use of the assumption that the string has not more than 1000 characters.  
        temp=new char[1001*2];  
        int[] z=new int[1001 * 2];  
        int L=0, R=0;  
        int len=s.length();  

        for(int i=0;i<len*2+1;i++){  
            temp[i]='.';  
        }  

        for(int i=0;i<len;++i){  
            temp[i*2+1] = s.charAt(i);  
        }  

        z[0]=1;  
        len=len*2+1;  

        for(int i=0;i<len;i++){  
            int ii = L - (i - L);     
            int n = R + 1 - i;  
            if (i > R)  
            {  
                z[i] = match(i, i,len);  
                L = i;  
                R = i + z[i] - 1;  
            }  
            else if (z[ii] == n)  
            {  
                z[i] = n + match(i-n, i+n,len);  
                L = i;  
                R = i + z[i] - 1;  
            }  
            else  
            {  
                z[i] = (z[ii]<= n)? z[ii]:n;  
            }   
        }  

        int n = 0, p = 0;  
        for (int i=0; i<len; ++i)  
            if (z[i] > n)  
                n = z[p = i];  

        StringBuilder result=new StringBuilder();  
        for (int i=p-z[p]+1; i<=p+z[p]-1; ++i)  
            if(temp[i]!='.')  
                result.append(String.valueOf(temp[i]));  

        return result.toString();  
    }  
}  

您可以从 我自己的博客。

Answer 17

这里我写了一个逻辑试试：）

public class palindromeClass{

public  static String longestPalindromeString(String in) {
        char[] input = in.toCharArray();
        int longestPalindromeStart = 0;
        int longestPalindromeEnd = 0;

        for (int mid = 0; mid < input.length; mid++) {
            // for odd palindrome case like 14341, 3 will be the mid
            int left = mid-1;
            int right = mid+1;
            // we need to move in the left and right side by 1 place till they reach the end
            while (left >= 0 && right < input.length) {
                // below check to find out if its a palindrome
                if (input[left] == input[right]) {
                    // update global indexes only if this is the longest one till now
                    if (right - left > longestPalindromeEnd
                            - longestPalindromeStart) {
                        longestPalindromeStart = left;
                        longestPalindromeEnd = right;
                    }
                }
                else
                    break;
                left--;
                right++;
            }
            // for even palindrome, we need to have similar logic with mid size 2
            // for that we will start right from one extra place
            left = mid;
            right = mid + 1;// for example 12333321 when we choose 33 as mid
            while (left >= 0 && right < input.length)
            {
                if (input[left] == input[right]) {
                    if (right - left > longestPalindromeEnd
                            - longestPalindromeStart) {
                        longestPalindromeStart = left;
                        longestPalindromeEnd = right;
                    }
                }
                else
                    break;
                left--;
                right++;
            }


        }
        // we have the start and end indexes for longest palindrome now
        return in.substring(longestPalindromeStart, longestPalindromeEnd + 1);
    }
public static void main(String args[]){
System.out.println(longestPalindromeString("HYTBCABADEFGHABCDEDCBAGHTFYW12345678987654321ZWETYGDE"));
}

}

Answer 18

该解决方案的复杂度为 O(n^2)。 O(1) 是空间复杂度。

public class longestPalindromeInAString {

        public static void main(String[] args) {
            String a =  "xyMADAMpRACECARwl"; 
            String res = "";
            //String longest = a.substring(0,1);
            //System.out.println("longest => " +longest);
            for (int i = 0; i < a.length(); i++) {
                String temp = helper(a,i,i);//even palindrome
                if(temp.length() > res.length()) {res = temp ;}
                temp = helper(a,i,i+1);// odd length palindrome
                if(temp.length() > res.length()) { res = temp ;}

            }//for
            System.out.println(res);
            System.out.println("length of " + res + " is " + res.length());

        }

        private static String helper(String a, int left, int right) {
            while(left>= 0 && right <= a.length() -1  &&  a.charAt(left) == a.charAt(right)) {
                left-- ;right++ ;
            }
            String curr = a.substring(left + 1 , right);
            System.out.println("curr =>" +curr);
            return curr ;
        }

    }

Answer 19

#longest palindrome
s='HYTBCABADEFGHABCDEDCBAGHTFYW123456789987654321ZWETYGDE'
out1=[]
def substring(x):
    for i in range(len(x)):
        a=x[i:]
        b=x[:-i]
        out1.append(a)
        out1.append(b)
        
    return out1

for i in range(len(s)):
    substring(s[i:])    
final=set([item for item in out1 if len(item)>2])
final
palind={item:len(item) for item in final if item==item[::-1]}
print(palind)
sorted(palind.items(),reverse=True, key=lambda x: x[1])[0]

{“DED”：3，“123456789987654321”：18，“67899876”：8，“ABCDEDCBA”：9，“456789987654”：12，“34567899876543”：14，“BCDEDCB”：7，“ABA”：3， ' 5678998765'：10，'2345678998765432'：16，'CDEDC'：5，'789987'：6，'8998'：4}
('123456789987654321', 18)

Answer 20

编程从给定字符串中查找最长的回文子串。

 package source;
    
    import java.util.ArrayList;
            
    public class LongestPalindrome 
    {
        //Check the given string is palindrome by 
        public static boolean isPalindrome (String s)
        {
            StringBuffer sb = new StringBuffer(s);
            if(s.equalsIgnoreCase(sb.reverse().toString()))
                return true;
            else
                return false;
        }
    
        public static void main(String[] args) 
        {
            //String / word without space
            String str = "MOMABCMOMOM"; // "mom" //abccbabcd
            
            if(str.length() > 2 )
            {
                StringBuffer sb = new StringBuffer();
                ArrayList<String> allPalindromeList = new ArrayList<>();
                        
                for(int i=0; i<str.length(); i++)
                {
                    for(int j=i; j<str.length(); j++)
                    {
                        sb.append(str.charAt(j));
                        if( isPalindrome(sb.toString()) ) {
                            allPalindromeList.add(sb.toString());                       
                        }
                    }
                    //clear the stringBuffer
                    sb.delete(0, sb.length());
                }
                 
                int maxSubStrLength = -1;
                int indexMaxSubStr = -1;
                int index = -1;
                
                for (String subStr : allPalindromeList) {
                    ++index;
                    if(maxSubStrLength < subStr.length()) {
                        maxSubStrLength = subStr.length();
                        indexMaxSubStr = index;
                    }
                }
                if(maxSubStrLength > 2)
                    System.out.println("Maximum Length Palindrome SubString is : "+allPalindromeList.get(indexMaxSubStr));
                else
                    System.out.println("Not able to find a Palindrome who is three character in length!!");
            
            }
        }
    
    }

Answer 21

这是我的算法：

1）将当前中心设置为第一个字母

2）同时向左和向右扩展，直到找到当前中心周围的最大回文

3）如果找到的回文比之前的回文大，则更新4

) 将当前中心设置为下一个字母

5) 对字符串中的所有字母重复步骤 2) 到 4)

这在 O(n) 中运行。

希望能帮助到你。

Answer 22

参考：Wikipedia.com

我发现的最好的算法，复杂度为 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;
  }    
}

Answer 23

我的解决方案是：

static string GetPolyndrom(string str)
{
    string Longest = "";

    for (int i = 0; i < str.Length; i++)
    {
        if ((str.Length - 1 - i) < Longest.Length)
        {
            break;
        }
        for (int j = str.Length - 1; j > i; j--)
        {
            string str2 = str.Substring(i, j - i + 1);
            if (str2.Length > Longest.Length)
            {
                if (str2 == str2.Reverse())
                {
                    Longest = str2;
                }
            }
            else
            {
                break;
            }
        }

    }
    return Longest;
}