Хибне відчуття безпеки
Фредді винайшов новий метод вирощування значно більших цвітних капуст. Він хоче поділитися цим відкриттям зі своїм колегою-садівником Томмі, але не хоче, щоб хтось інший дізнався про цей метод. Тому двоє садівників вирішили використовувати просту техніку шифрування, запропоновану М. Е. Охавером.
Шифрування базується на азбуці Морзе, яка представляє символи як послідовності змінної довжини з точок і тире. Нижче наведена таблиця з послідовностями азбуки Морзе для всіх літер:
Зверніть увагу, що чотири можливі комбінації точок і тире не призначені. Для цілей цієї задачі ми призначимо їх наступним чином (зверніть увагу, що це не призначення для фактичної азбуки Морзе):
На практиці символи в повідомленні розділяються короткими паузами, зазвичай відображаються як пробіли. Таким чином, повідомлення ACM GREATER NY REGION кодується як:
.- -.-. – ..– –. .-. . .- - . .-. ..– -. -.– ..– .-. . –. .. — -.
Схема шифрування Охавера базується на спотворенні азбуки Морзе, а саме на видаленні пауз між літерами. Оскільки паузи необхідні (оскільки Морзе є кодуванням змінної довжини, яке не є префіксно-вільним), додається рядок, що ідентифікує кількість точок і тире в кожному символі. Наприклад, розглянемо повідомлення ".–.-.–". Без знання, де повинні бути паузи, це може бути "ACM", "ANK", або кілька інших можливостей. Якщо ми додамо інформацію про довжину, наприклад ".–.-.– 242", тоді код є однозначним.
Схема Охавера має три кроки, однакові для шифрування та дешифрування:
Перетворити текст в азбуку Морзе без пауз, але з рядком чисел для позначення довжин коду.
Перевернути рядок чисел.
Перетворити точки і тире назад у текст, використовуючи перевернутий рядок чисел як довжини коду.
Як приклад, розглянемо зашифроване повідомлення "AKADTOF IBOETATUK IJN". Перетворення в азбуку Морзе з рядком довжин дає:
.–.-.–..—-..-...–..-...—.-.–..–.-..–...—-. 232313442431121334242
Перевернувши числа і декодуючи, ми отримуємо оригінальне повідомлення "ACM GREATER NY REGION".
Безпека цієї схеми кодування не надто висока, але Фредді вважає, що цього достатньо для його цілей. Чи допоможете ви Фредді реалізувати цей алгоритм кодування і захистити його конфіденційну інформацію?
Вхідні дані
Вхідні дані складатимуться з кількох повідомлень, закодованих за алгоритмом Охавера, кожне з яких на одному рядку. Кожне повідомлення використовуватиме лише двадцять шість великих літер, підкреслення, коми, крапки та знаки питання. Повідомлення не перевищуватимуть 1000 символів у довжину.
Вихідні дані
Для кожного повідомлення на вході виведіть декодоване повідомлення на одному рядку.