Условие:
Вам даны две строки t и s длины n, состоящие из маленьких латинских букв (от 'a' до 'z').
Определите, можно ли t получить из s следующим преобразованием:
сначала можно сделать циклический сдвиг строки s на любую величину k влево (например, из «abcd» можно получить «bcda», «cdab» и «dabc»);
затем можно применить шифр Цезаря: выбрать целое число d и заменить каждую букву на предшествующую ей на d позиций в алфавите (например, для строки «abxy» и d = 2 получится «yzvw»).
Выведите ответ — можно ли получить t из s описанным преобразованием.
Входные данные
В первой строке дано одно целое число n — длина строк (1 ≤ n ≤ 200 000).
Во второй строке дана строка t, состоящая из n строчных латинских символов.
В третьей строке содержится строка s, состоящая из n строчных латинских символов.
Выходные данные
Если не существует описанного преобразования, которое переведёт строку s в строку t, выведите «Impossible» (без кавычек).
Иначе, выведите «Success», а во второй строке выведите два числа k и d, описывающие преобразование, переведшее строку s в строку t (0 ≤ k < n, -26 < d < 26). Если различных подходящих ответов несколько, вы можете вывести любой из них.
Решение:
Для решения задачи, нам нужно проверить, можно ли получить строку t из строки s с помощью двух операций: циклического сдвига и шифра Цезаря. Вот шаги, которые мы будем выполнять: 1. Циклический сдвиг: Мы можем создать все возможные циклические сдвиги строки s и проверить, можно ли с помощью шифра Цезаря получить строку t из любого из этих сдвигов. 2. Шифр Цезаря: Для каждой пары символов из сдвинутой строки и строки t мы можем вычислить значение d, которое определяет, на сколько позиций нужно сдвинуть буквы в алфавите. 3. Проверка всех сдвигов: Мы будем проверять все возможные сдвиги стро...
1. Мы перебираем все возможные значения от до , чтобы получить все циклические сдвиги строки . 2. Для каждого сдвига мы вычисляем для первого символа. 3. Затем проверяем, подходит ли это значение для всех остальных символов. 4. Если мы находим подходящий сдвиг и значение , выводим Success и значения и . 5. Если ни один из сдвигов не подходит, выводим Impossible. - Мы используем модуль 26 для работы с алфавитом, чтобы избежать выхода за пределы букв. - Значение может быть приведено к диапазону для соответствия условиям задачи.