ЛОШ 2013: Командная олимпиада

Биологи Карельского Мутационного Проекта (КМП) недавно решили начать новые исследования, которые должны доказать, что люди — близкие родственники мамонтов. Чтобы доказать это странное предположение, ученые планируют сравнить ДНК людей и мамонтов.

Для сравнения ДНК разделяется на фрагменты длины n и они последовательно сравниваются. Поскольку в процессе развития у людей и мамонтов могли происходить мутации, предлагается следующий способ сравнения фрагментов.

Рассмотрим строку α. Будем говорить, что α мутирует в β, если α = xyz для некоторых (возможно пустых) x, y и z, а β = xy^Rz, где y^R означает строку y, записанную задом наперед (например, "abc"^R = "cba"). Будем говорить, что строки α и β похожи, если α может быть превращена в β не более чем за 4 мутации.

По двум данным фрагментам ДНК определите, похожи ли они.