Расшифровать зашифрованную строку

Допустим, есть определенный способ шифрования строк:

• Добавьте символ $, который является первым символом в алфавите, в конце строки.
• Сформируйте все строки, которые мы получаем, непрерывно перемещая первый символ в конец строки.
• Сортируйте все строки, которые мы получили, в алфавитном порядке.
• Сформируйте новую строку, добавив к ней последний символ каждой строки.

Например, слово FRUIT зашифровано следующим образом:

We append the character $ at the end of the word:
FRUIT$

We then form all the strings by moving the first character at the end:
FRUIT$
RUIT$S
UIT$FR
IT$FRU
T$FRUI
$FRUIT

Then we sort the new strings into alphabetical order:
$FRUIT
FRUIT$
IT$FRU
RUIT$F
T$FRUI
UIT$FR

The encrypted string:
T$UFIR

Теперь моя проблема очевидна: как расшифровать данную строку в ее первоначальном виде.

Я уже пол недели бьюсь головой, и у меня наконец закончилась бумага.

Как мне покончить с этим?

Что я обнаружил:

если у нас есть последний шаг шифрования:

$FRUIT
FRUIT$
IT$FRU
RUIT$F
T$FRUI
UIT$FR

Мы можем знать первый и последний символ исходной строки, поскольку самый правый столбец — это сама зашифрованная строка, а самый левый столбец всегда в алфавитном порядке. Последний символ является первым символом зашифрованной строки, поскольку $ всегда является первым в алфавите и существует только один раз в строке. Затем, если мы находим символ $ в крайнем правом столбце и ищем символ в той же строке в крайнем левом столбце, мы получаем первый символ.

Итак, что мы можем знать о зашифрованной строке T $ UFIR, так это то, что исходной строкой является F *** T $, где * — неизвестный символ.

Там заканчиваются мои идеи. Теперь я должен использовать всемирную паутину и спросить другого человека: как?

Вы можете сказать, что это домашнее задание, и, будучи знакомым с моим преподавателем, я ставлю на то, что это проблема динамического программирования.