ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

1423. Басня о строке

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ

Вступление

Я хочу рассказать Вам одну историю. Не всю, конечно, а только начало, потому что конец этой истории стал легендой программирования — так же, как и её непосредственные участники.
Когда компьютеры были большими, деревья маленькими, а солнце светило ярче… Короче говоря, жили-были Три Программиста. Вряд ли они участвовали в контестах, поскольку никаких контестов в те далёкие времена ещё не было. Не было ACM ICPC, не было даже Timus Online Judge. А Три Программиста — были.

Задача

Однажды Три Программиста придумали занятную игру для тренировки памяти и умственных способностей. Первый Программист сочинил строку S из N символов и сообщил её Второму и Третьему Программистам. Второй Программист произвёл над этой строкой X (0 ≤ X < N) последовательных циклических сдвигов (под циклическим сдвигом строки понимается перенос её последнего символа в начало). В результате этих манипуляций получилась строка T, которую он сообщил Третьему Программисту. Задачей Третьего Программиста было определить число X, либо сообщить Второму Программисту, что он ошибся, поскольку строка T не могла быть получена из строки S с помощью циклических сдвигов.

Исходные данные

Первая строка содержит целое число N (1 ≤ N ≤ 250000). Вторая строка содержит строку S. Третья строка содержит строку T. Обе строки имеют длину N и могут содержать любые символы таблицы ASCII с кодами от 33 до 255.

Результат

Если строка T может быть получена из строки S с помощью циклических сдвигов, выведите искомое число X, иначе выведите «−1». Если задача имеет несколько решений, можно вывести любое из них.

Пример

исходные данныерезультат
11
abracadabra
racadabraab
9

Замечания

Рассмотрим строки S = «abracadabra» и T = «racadabraab». Строка T может быть получена из строки S с помощью 9 циклических сдвигов: «abracadabra» > «aabracadabr» > «raabracadab» > «braabracada» > «abraabracad» > «dabraabraca» > «adabraabrac» > «cadabraabra» > «acadabraabr» > «racadabraab».
Автор задачи: Никита Рыбак, Илья Гребнов, Дмитрий Ковалёв
Источник задачи: Timus Top Coders: First Challenge