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

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

我知道如何在O（n ^ 2）中执行此操作。 但似乎存在更好的解决方案。

我发现了这个 ，并且有一个O（n）答案的链接，但它是用Haskell编写的，对我来说并不清楚。

在c＃或类似的地方获得答案会很棒。

Answer 1

我在这里找到了解决方案的清晰解释。 感谢Justin的链接。

在那里你可以找到算法的Python和Java实现（C ++实现包含错误）。

这里是C＃实现，它只是这些算法的翻译。

public static int LongestPalindrome(string seq) { int Longest = 0; List l = new List(); int i = 0; int palLen = 0; int s = 0; int e = 0; while (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 l = new ArrayList(); 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 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 4

我接受采访时得到了这个问题。

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

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

Answer 5

 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 6

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