Арифметика и числовые алгоритмы

Летние учебно-тренировочные сборы, Петрозаводск, 30 августа 2006 года

Задача H. ДНК роботов

Имя входного файла	robots.in
Имя выходного файла	robots.out
Ограничение по времени	2 секундs
Ограничение по памяти	64 мегабайта

Используя недавно открытые методы искусственного конструирования ДНК, ученые НИИ Данных Строк (НИИ ДС) начали величайший эксперимент по строительству биологических роботов.

Для упрощения необходимого программного обеспечения было принято решение использовать ДНК из M = 2ⁿ (2 ≤ n)символов. Более того, по техническим причинам в ДНК роботов использованы не обычные строки, а циклические, поэтому их можно читать с любого места.

Среди вопросов, которые планируется исследовать в ходе эксперимента, особый интерес представляет анализ мутаций роботов. После длительного периода наблюдений были обнаружены несколько типов роботов. При попытке восстановить дерево мутаций ученые НИИ ДС столкнулись со следующей задачей: им необходима программа для вычисления коэффициента совпадения ДНК двух роботов. Коэффициент совпадения двух ДНК – это количество букв, которые в них совпадут, если циклически сдвинуть вторую ДНК относительно первой наиболее удачным образом, то есть так, чтобы число совпадающих букв было как можно больше.

Вам нужно написать программу, вычисляющую коэффициент совпадения.

Формат входного файла

В первой строке входного файла записано одно число M (4 ≤ М ≤ 131 072). Следующие две строки содержат ДНК, которые необходимо исследовать. Обе эти строки содержат ровно М символов, каждый из которых – это одна из следующих латинских букв: 'A', 'C', 'G' или 'T' (они обозначают аденин, цитозин, гуанин или тимин, соответственно).

Пример

robots.in	robots.out
16 ACGTACGTACGTACGT CGTACGTACGTACGTC	15 1