Extraction des sous-chaînes palindromes — exercice corrigé de Python (école d'ingénieur) (chapitre 1)

Extraction des sous-chaînes palindromes

Bases de Python, variables et types

Énoncé

Écrire une fonction extraire_palindromes(chaine) qui retourne tous les palindromes (de longueur $\geq 2$ ) d'une chaîne en complexité $O (n^{2})$ .

Corrigé

def extraire_palindromes_optimise(chaine):
    n = len(chaine)
    palindromes = set()

    def expandir(gauche, droite):
        while gauche >= 0 and droite < n and chaine[gauche] == chaine[droite]:
            if droite - gauche + 1 >= 2:
                palindromes.add(chaine[gauche:droite+1])
            gauche -= 1
            droite += 1

    for centre in range(n):
        expandir(centre, centre)      # Impair
        expandir(centre, centre + 1)  # Pair
    return list(palindromes)

Explication : L'algorithme naïve en $O (n^{3})$ vérifie toutes les sous-chaînes possibles. La version optimisée en $O (n^{2})$ s'étend depuis les $2 n - 1$ centres de symétrie possibles.