编写一个返回给定string中最长回文的函数

例如string“abaccddccefe”中的“ccddcc”

我想到了一个解决scheme，但它运行在O（n ^ 2）时间

Algo 1：

步骤：它是一个蛮力方法

  1. 有2个循环
    对于i = 1到i小于array.length -1
    对于j = i + 1到j小于array.length
  2. 这样你可以得到数组中每个可能组合的子串
  3. 有一个回文函数，检查一个string是回文
  4. 所以对于每个子string（i，j）调用这个函数，如果它是一个回文存储在一个stringvariables
  5. 如果发现下一个回文子string，并且大于当前string，则将其replace为当前string。
  6. 最后你的stringvariables将有答案

问题：1.这个algorithm运行在O（n ^ 2）时间。

Algo 2：

  1. 反转string并将其存储在不同的数组中
  2. 现在find两个数组之间最大的匹配子串
  3. 但是这也运行在O（n ^ 2）时间

你们能想到一个在更好的时间运行的algorithm吗？ 如果可能的话O（n）时间

您可以在O(n)时间使用Manacher's Algorithmfind最长的回文。 它的实现可以在这里和这里find。
对于inputString s = "HYTBCABADEFGHABCDEDCBAGHTFYW1234567887654321ZWETYGDE" 。 它find正确的输出是1234567887654321 。

Algo 2可能不适用于所有的string。 这是一个这样的string“ABCDEFCBA”的例子。

不是说string有“ABC”和“CBA”作为它的子string。 如果你反转原始string，它将是“ABCFEDCBA”。 最长的匹配子string是不是回文的“ABC”。

您可能需要另外检查这个最长的匹配子string是否是一个运行时间为O（n ^ 3）的回文。

就我所了解的问题而言，我们可以在中心索引周围find回文，并在中心的左右两边search。 鉴于这一点，并知道input的angular落没有回文，我们可以设置边界为1和长度为1。 在注意string的最小和最大边界的同时，我们validation对称索引（右和左）位置处的字符对于每个中心位置是否相同直到达到我们的最大上限中心。

外部循环是O（n）（max n-2次迭代），内部while循环是O（n）（max（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

与正则expression式和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

最近我被问到这个问题。 这是我最终提出的解决scheme。 我在JavaScript中做了这个，因为这种语言非常简单。

基本的概念是，你走string寻找可能的最小的多字符回文（两个或三个字符之一）。 一旦你有了，扩大两边的边界，直到它不再是回文。 如果这个长度比当前最长的长度长，那么将其存储并移动。 

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

这绝对可以清理和优化多一点，但它应该有一个很好的performance，除了最坏的情况下（一串字母）。

嗨这是我的代码findstring中最长的回文。 请参阅以下链接了解http://stevekrenzel.com/articles/longest-palnidromealgorithm

使用的testing数据是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; }

参见关于这个主题的维基百科文章 。 线性O（n）解决scheme示例Manacheralgorithm Java实现，请参见下面的文章：

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]<(ri)) { p[i] = p[i2]; m = -1; // This signals bypassing the while loop below. } else { p[i] = ri; 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; } }

一个有效的Regexp解决scheme，避免暴力

从整个string长度开始，向下工作到2个字符，只要匹配成功就存在

对于"abaccddccefe"则expression式testing7匹配返回ccddcc之前。

（。）（）（）（）（）（）（\ 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 

 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

试试string – “HYTBCABADEFGHABCDEDCBAGHTFYW123456789987654321ZWETYGDE”; 它应该为偶数和奇数的朋友工作。 非常感谢Mohit！

使用命名空间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; }

下面的代码计算Palidrom的长度和奇数长度的string。

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

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; }
  1. 修改string来分隔每个字符使用分隔符[这是纳入奇数和偶数回文]
  2. find每个angular色周围的回文，把它当作一个中心

我们可以用这个find所有长度的回文。

示例：

word = abcdcbc

modifiedString = a＃b＃c＃d＃c＃b＃c

palinCount = 1010105010301

最长的回文长度= 5;

最长的回文= bcdcb

公共类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; } }

}

在这里我写了一个逻辑尝试它:) 

 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("abbabbaxabbabba toppottoppottoppot abbabbayabbabba")); } }

这将从给定的string返回最长的回文string 

 -(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"]; }

==输出===

input：abcccde输出：ccc

input：abcccbd输出：bcccb

input：abedccde输出：edccde

input：abcccdeed输出：契据

input：abcccbadeed输出：abcccba

以下是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');

我出于好奇，简单和自我解释的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); } }

对于线性解决scheme，可以使用Manacheralgorithm。 还有另一个algorithm调用Gusfieldalgorithm，下面是java中的代码： 

 public class Solution { char[] temp; public int match(int a, int b,int len){ int i = 0; while (ai>=0 && b+i<len && temp[ai] == 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(in, 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=pz[p]+1; i<=p+z[p]-1; ++i) if(temp[i]!='.') result.append(String.valueOf(temp[i])); return result.toString(); } }

你可以从我自己的博客上find更多的解决scheme，比如最好的O（n ^ 2）解决scheme或Manacheralgorithm。

这是我的algorithm：

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

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

3）如果你发现回文大于前回文，更新它

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

5）对string中的所有字母重复步骤2）至4）

这在O（n）中运行。

希望它有帮助。

我发现的最好的algorithm，复杂度为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]<(ri)) { p[i] = p[i2]; m = -1; // This signals bypassing the while loop below. } else { p[i] = ri; 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; } }

我的解决scheme是： 

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

    如何find最长的回文序列？

    在使用后缀树的string中最长的回文

    Manacheralgorithm（在线性时间内find最长回文子串的algorithm）

    如何使用Python逻辑来检查回文

    检查回文string

    如何检查一个string是使用正则expression式的回文？