Tâche «Déchiffrement d'un décalage cyclique de chaîne»

Soit une chaîne chiffrée S composée de lettres latines minuscules. Elle a été obtenue à partir de la chaîne originale T par un décalage cyclique vers la droite d'un certain nombre de positions k (0 ≤ k < |T|) suivi du remplacement de chaque caractère par le suivant dans l'alphabet (avec transition cyclique : 'z' → 'a'). Il faut trouver la chaîne originale T de longueur minimale telle qu'après la transformation décrite on obtienne S. S'il existe plusieurs T de ce type, choisir la chaîne lexicographiquement minimale. La longueur de S est de 1 à 1000. Il est garanti qu'une solution existe.

Exemple 1

Exemple 2

Exemple 3