如何找到給定字符串中最長的迴文？

Question

可能重複：
Write a function that returns the longest palindrome in a given string

我知道如何爲O做到這一點（N^2）。但似乎有一個更好的解決方案。

我找到了this，並有一個O（n）答案的鏈接，但它是用Haskell編寫的，對我來說不是很清楚。

用c＃或類似的方式獲得答案會很棒。

Answer 1

我發現解決方案的明確解釋here。感謝賈斯汀爲此鏈接。

在那裏你可以找到該算法的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 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; 
    }