Республиканская олимпиада по информатике, 2012 год, 9 класс

(ДНК)

Ограничение по времени:

2 секунды

Ограничение по памяти:

64 мегабайта

Одна из задач генетического анализа заключается в определении степени похожести двух последовательностей нуклеотидов. Последовательность нуклеотидов — это строка из букв $A,$ $G,$ $C,$ $T.$ Последовательности можно циклически сдвигать друг относительно друга. Степенью похожести двух последовательностей назовем максимально возможное количество совпадений символов в соответствующих позициях строк. Для заданных двух последовательностей определите степень их похожести.

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

Входной файл содержит две строки одинаковой длины, состоящие из символов $A,$ $G,$ $C,$ $T.$ Строки не пустые и их длина не превышает 50000.

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

На первой строке выходного файла выведите целое число — степень похожести заданных строк. На следующих двух строках выведите исходные строки, циклически сдвинутые так, что достигается полученная степень похожести. Строки выводите в таком же порядке, как они даны во входном файле.

Примеры:

Вход

ACAGTG
AGTGTC

Ответ

5
ACAGTG
TCAGTG

Замечание

В не менее $50\%$ тестов длина каждой строки не превышает 10000