Écrivez une fonction qui renvoie le palindrome le plus long dans une chaîne de caractères donnée.

Question

Par exemple, "ccddcc" dans la chaîne "abaccddccefe".

J'ai pensé à une solution mais elle fonctionne en temps O(n^2).

Algo 1 :

Des étapes : C'est une méthode de force brute

1. Avoir 2 boucles for
   pour i = 1 à i inférieur à array.length -1
   pour j=i+1 à j inférieur à array.length
2. De cette façon, vous pouvez obtenir la sous-chaîne de chaque combinaison possible à partir du tableau.
3. Avoir une fonction palindrome qui vérifie si une chaîne est palindrome.
4. ainsi, pour chaque sous-chaîne (i,j), appelez cette fonction, si c'est un palindrome, stockez-le dans une variable de type chaîne.
5. Si vous trouvez la prochaine sous-chaîne palindrome et si elle est supérieure à la sous-chaîne actuelle, remplacez-la par la sous-chaîne actuelle.
6. Enfin, votre variable chaîne de caractères contiendra la réponse

Questions : 1. Cet algorithme fonctionne en temps O(n^2).

Algo 2 :

1. Inversez la chaîne de caractères et stockez-la dans un tableau différent.
2. Maintenant, trouvez la plus grande sous-chaîne correspondante entre les deux tableaux.
3. Mais cela aussi fonctionne en temps O(n^2)

Pouvez-vous penser à un algo qui fonctionne dans un meilleur délai ? Si possible en temps O(n)

Answer 1

Vous pouvez trouver le plus long palindrome en utilisant Algorithme de Manacher sur O(n) temps ! Sa mise en œuvre peut être trouvée ici et ici .

Pour la saisie String s = "HYTBCABADEFGHABCDEDCBAGHTFYW1234567887654321ZWETYGDE" il trouve la sortie correcte qui est 1234567887654321 .

Answer 2

L'Algo 2 peut ne pas fonctionner pour toutes les chaînes. Voici un exemple d'une telle chaîne "ABCDEFCBA".

Pas que la chaîne a "ABC" et "CBA" comme sous-chaîne. Si vous inversez la chaîne originale, vous obtiendrez "ABCFEDCBA" et la plus longue sous-chaîne correspondante est "ABC", qui n'est pas un palindrome.

Vous pouvez avoir besoin de vérifier en plus si la plus longue sous-chaîne correspondante est en fait un palindrome, ce qui a un temps d'exécution de O(n^3).

Answer 3

D'après ce que j'ai compris du problème, nous pouvons trouver des palindromes autour d'un index central et étendre notre recherche dans les deux sens, à droite et à gauche du centre. Sachant cela et sachant qu'il n'y a pas de palindrome aux coins de l'entrée, nous pouvons fixer les limites à 1 et à la longueur 1. Tout en faisant attention aux limites minimum et maximum de la chaîne, nous vérifions si les caractères aux positions des index symétriques (droite et gauche) sont les mêmes pour chaque position centrale jusqu'à ce que nous atteignions notre centre de limite supérieure maximum.

La boucle externe est O(n) (n-2 itérations au maximum), et la boucle while interne est O(n) (environ (n / 2) - 1 itérations au maximum).

Voici mon implémentation Java en utilisant l'exemple fourni par d'autres utilisateurs.

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

Le résultat de cette opération est le suivant :

marcello:datastructures marcello$ javac LongestPalindrome
marcello:datastructures marcello$ java LongestPalindrome
String: HYTBCABADEFGHABCDEDCBAGHTFYW12345678987654321ZWETYGDE
Longest Palindrome: 12345678987654321

Answer 4

Une efficacité Regexp solution qui évite la force brute

Commence par la longueur totale de la chaîne et descend jusqu'à 2 caractères, existe dès qu'une correspondance est établie

Pour "abaccddccefe" la regexp teste 7 correspondances avant de retourner 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

fonction

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 5

Cette question m'a été posée récemment. Voici la solution que j'ai [finalement] trouvée. Je l'ai réalisée en JavaScript car elle est assez simple dans ce langage.

Le concept de base est que vous parcourez la chaîne de caractères à la recherche du plus petit palindrome à plusieurs caractères possible (soit un palindrome à deux ou trois caractères). Une fois que vous l'avez trouvé, élargissez les frontières des deux côtés jusqu'à ce que le palindrome cesse d'être un palindrome. Si cette longueur est supérieure à celle du palindrome actuel, enregistrez-la et continuez.

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

Ce système pourrait certainement être nettoyé et optimisé un peu plus, mais il devrait avoir de bonnes performances, sauf dans le pire des cas (une chaîne de caractères de la même lettre).