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}. \OutputFile Выведите в выходной файл "\textbf{Similar}", если строки похожи, и "\textbf{Different}", если нет.
Лимит времени 1 секунда
Лимит использования памяти 64 MiB
Входные данные #1
ATGAATGA
AGGAATTA
Выходные данные #1
Similar