Шифр#494

Шифр (Розбір)

Автор, розробник, автор розбору: Тимур Дегтеарі

У цій задачі ми можемо скористатися малими обмеженнями на довжину імені (не більше ) та довжину повідомлення (не більше ). Це дозволяє нам з комфортом використовувати рішення з складністю O(n \cdot m) або навіть O(n \cdot m^2).

Ми перебираємо всі можливі початкові позиції, де закодоване ім'я може з'явитися в повідомленні. Зокрема, ми пробуємо кожну позицію від до n - m + 1 як потенційний початковий індекс.

Для кожної кандидатної позиції ми розглядаємо підрядок a[i], a[i+1], \ldots, a[i+m-1] і намагаємося зіставити кожне число з відповідною літерою з імені. Під час цього процесу ми перевіряємо, що:

  • Кожна літера в імені відповідає точно одному числу.

  • Жодні дві різні літери не відповідають одному й тому ж числу (тобто, відображення є ін'єктивним).

Якщо ця властивість виконується, ми знайшли дійсний шифр. Потім ми довільно призначаємо залишкові невикористані числа літерам, які не з'являються в імені (оскільки ці призначення не вплинуть на вже зіставлений підрядок) і виводимо результат.

Якщо властивість не виконується для всіх позицій, ми повідомляємо, що жоден дійсний шифр не існує.

Часова складність: O(n \cdot m), де — довжина зашифрованого повідомлення, а — довжина імені.