EduBrick

M. Вхождения с поворотом алфавита

3000 мс · 256 МБ · всё или ничего

Найдите все вхождения образца pp в текст tt с точностью до поворота алфавита: подходит позиция ll, если при каком-то общем dd каждая буква окна получается из соответствующей буквы pp сдвигом на dd по кругу.

Формат ввода

В первой строке - текст tt, во второй - образец pp.

Обе строки непусты, состоят из строчных латинских букв, длины не превосходят 2⋅1052 \cdot 10^5.

Формат вывода

В первой строке - количество вхождений.

Во второй - позиции начала по возрастанию, нумерация с единицы. Если вхождений нет, вторая строка пустая.

Примеры

ввод
abcxyz
bcd
вывод
2
1 4
ввод
ab
abc
вывод
0

Разбор идеи от автора задачи. Сначала попробуйте сами.
Войдите, чтобы отправлять решения.