Comment trouver le plus long palindrome d'une chaîne donnée?

Question

Possible en double:
Write a function that returns the longest palindrome in a given string

Je sais comment faire en O (n^2). Mais il semble qu'il existe une meilleure solution.

J'ai trouvé this, et il y a un lien vers O (n) answer, mais il est écrit en Haskell et n'est pas clair pour moi.

Ce serait génial d'obtenir une réponse en C# ou similaire.

Answer 1

J'ai trouvé une explication claire de la solution here. Merci à Justin pour ce lien.

Vous pouvez y trouver des implémentations Python et Java de l'algorithme (l'implémentation C++ contient des erreurs).

Et voici l'implémentation C# qui est juste une traduction de ces algorithmes.

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

Et voici sa version 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

Récemment, j'écrit le code suivant lors d'un entretien ...

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

Je suis arrivé à cette question quand je pris une interview.

J'ai découvert quand j'étais à la maison, malheureusement.

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#

D'abord, je cherche même palindromes de longueur. Ensuite, je cherche des palindromes de longueur impaire. Quand il trouve un palindrome, il détermine la longueur et définit la longueur maximale en conséquence. La complexité moyenne des cas est linéaire.

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