Information

Author(s) Virginie Van den Schreick
Deadline No deadline
Submission limit No limitation

Sign in

Mission 4 : Recherche du plus long palindrome

Un palindrome est un mot dont l’ordre des caractères reste le même qu’on le lise de gauche à droite ou de droite à gauche, comme radar ou kayak. Votre objectif dans cet exercice est de trouver le plus long palindrome contenu dans une chaîne de caractères, et d'en renvoyer la longueur.

Détecter le plus long palindrome dans une chaîne de caractères est un problème compliqué. En informatique, lorsqu'on est face à un problème compliqué, la meilleure approche pour le résoudre est de le découper en petits problèmes plus simples. Il suffit ensuite d'écrire une méthode pour résoudre chaque sous-problème, et de combiner ces méthodes pour résoudre le problème compliqué.

Pour rechercher le plus long palindrome, une piste est d'abord d'écrire une méthode permettant d'extraire d'une chaîne de caractères de longueur n les sous-chaînes de longueur n-1, n-2, etc. Notez que la classe String contient des méthodes qui pourraient vous aider pour cela.

Vous devez donc écrire une méthode dont la spécification est la suivante :

/*
 * @pre - s != null
 *
 * @post retourne la longueur du plus long palindrome trouvé dans s.
 */
public static int longueurPlusLongPalindrome(String s);

À titre d’exemple, le code ci-dessous :

System.out.println (longueurPluslongPalindrome ("KAYAKAK"));
System.out.println (longueurPluslongPalindrome ("AVABCD"));

Affiche les valeurs 5 et 3.

Pour résoudre ce problème, pensez à la découper en sous-problèmes et n’hésitez pas à utiliser une ou plusieurs méthodes privées supplémentaires.


Question 1:

Complétez ici le corps de la méthode longueurPlusLongPalindrome dont la spécification est donnée dans l'énoncé.

public static int longueurPlusLongPalindrome (String s)
Question 2:

Déclarez ici les méthodes privées que vous souhaitez utiliser pour décomposer le problème en sous-problèmes. Attention, veillez à n'utiliser que des méthodes de classe (static).