bzip2 – Épreuve régionale 2009

ENONCE

Le but de ce problème est d'étudier une fonction de transformation de données utilisée dans bzip2 (un algorithme de compression de données).

La transformation prend en entrée une chaîne de caractères s, de longueur n. Cette chaîne est placée à la première ligne d'un tableau de n lignes. Chaque nouvelle ligne du tableau est générée en prenant la ligne précédente décalée d'une case vers la droite.

Exemple : s = "PROLOGIN", n = 8. Le tableau sera :

1
2
3
4
5
6
7
8

P R O L O G I N
N P R O L O G I
I N P R O L O G
G I N P R O L O
O G I N P R O L
L O G I N P R O
O L O G I N P R
R O L O G I N P

La deuxième étape de la transformation consiste à classer les lignes du tableau par ordre alphabétique. On obtient donc sur notre exemple :

1
2
3
4
5
6
7
8

G I N P R O L O
I N P R O L O G
L O G I N P R O
N P R O L O G I
O G I N P R O L
O L O G I N P R
P R O L O G I N
R O L O G I N P

Enfin, l'étape finale consiste à renvoyer la chaîne de caractères correspondant à la dernière colonne du tableau trié (ici "OGOILRNP"), ainsi que le numéro de la ligne contenant la chaîne initiale, dans le tableau trié (ici : 7).

On vous demande de programmer la transformation inverse qui, à partir de la dernière colonne du tableau trié et de la position de la chaîne initiale, renvoie la chaîne initiale.

On garantie que la chaîne initiale existe toujours, et qu'il n'y a toujours qu'une seule solution.

ENTREE

• Sur la première ligne, un entier n, plus petit que 100.
• Sur la deuxième ligne, une chaîne de caractères correspondant à la dernière colonne du tableau trié, de taille n. Il n'y aura que des caractères majuscules.
• Sur la troisième ligne, le numéro de la ligne dans le tableau trié correspondant à la chaîne initiale.

SORTIE

Une chaîne de caractères : la chaîne initiale qui a été transformée.