Отримання знань

Задача Spy

(запропонована управлінням зовнішньої розвідки)

Шпигун, що давно був направлений у раніше ворожу, а тепер дружню країну, використовував для передачі повідомлень шифрувальну машинку, привезену із собою на початку кар'єри, отже – морально застарілу. Працював цей автомат так: у кожному слові повідомлення він змінював голосну букву на ланцюжок символів, що складався з цієї самої букви на початку, деякого кодового слова і знову цієї ж букви. Простий шифр, правда? Якщо врахувати, що машинка працювала тільки з малими буквами латинського алфавіту, секретне повідомлення "i like pivo" із використанням послідовності, що кодує "qa" на батьківщині героя одержували у вигляді "iqai liqaikeqae piqaivoqao". Усе було прекрасно, поки машинка від старості не почала кодувати те саме повідомлення по декілька разів. Допоможіть криптографам, що отримали повідомлення, відправлене несправною машинкою, його прочитати.

Технічні умови: Програма читає з клавіатури в першому рядку закодовану послідовність, у другому – послідовність, що кодує. Програма виводить на екран шуканий рядок. Кодований рядок не довше 255 символів, кодове слово не довше 255 символів.

Розв'язок задачі Spy 

Обмеження задачі дозволяють використати просту стратегію роз­в’язку. На кожному кроці припускаємо, що поточний рядок принаймні раз шифрувався і пробуємо його дешифрувати. За кожною голосною літерою намагаємося «знайти» кодове слово, а потім повинна слідувати та ж сама літера (звичайно, ті голосні літери, що опиняються в кодовому слові, пропускаємо). Процес припиняється, коли ми не змогли «знайти» кодове слово після якоїсь голосної літери, або коли лишилися одні приголосні літери.

Насправді, цей розв’язок не такий і поганий. На кожному кроці кількість голосних літер скорочується вдвічі, при цьому робиться один прохід по рядку. Отже, кількість операцій має порядок N*logN, де N – довжина закодованої послідовності.