eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Аналіз ДНК

Аналіз ДНК

Біологи Карельського Мутаційного Проекту (КМП) нещодавно вирішили розпочати нові дослідження, які повинні довечти, що люди --- близькі родичі мамонтів. Щоб довести це дивне припущення, вчені планують порівняти ДНК людей та мамонтів. Для порівняння ДНК розділяється на фрагменти довжини \textbf{n} і вони послідовно порівнюються. Оскільки у процесі розвитку у людей та мамонтів могли відбуватись мутації, пропонується наступний спосіб порівняння фрагментів. Розглянемо рядок \textbf{α}. Будемо казати, що \textbf{α} \textit{мутує} в \textbf{β}, якщо \textbf{α} = \textbf{xyz} для деяких (можливо порожніх) \textbf{x}, \textbf{y} і \textbf{z}, а \textbf{β} = \textbf{xy^Rz}, де \textbf{y^R} означає рядок \textbf{y}, записаний задом наперед (наприклад, "\textbf{abc}"^R = "\textbf{cba}"). Будемо казати, що рядки \textbf{α} та \textbf{β} \textit{схожі}, якщо \textbf{α} може бути перетворена в \textbf{β} не більше ніж за \textbf{4} мутації. За двома заданими фрагментами ДНК визначте, чи схожі вони. \InputFile Вхідний файл містить два рядки, які складаються з символів '\textbf{A}', '\textbf{D}', '\textbf{G}' та '\textbf{T}'. Рядки мають однакову довжину, яка не перевищує \textbf{30}. \textbf{Виідні дані} Виведіть у вихідний файл "\textbf{Similar}", якщо рядки схожі, і "\textbf{Different}", якщо ні.
Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB
Вхідні дані #1
ATGAATGA
AGGAATTA
Вихідні дані #1
Similar