- Описание
- Отправленные решения
428. Шифр подстановки
Подстановочный шифр заменяет каждый символ в сообщении на какой-либо ещё, при этом равные символы заменяются на равные, а различные — на различные. Например, при шифровании с помощью подстановочного шифра $e$ — $a$, $l$ — $b$, $o$ — $w$, $v$ — $c$ слово «love» оказывается зашифровано как «bwca».
Вам дана зашифрованная строка $t$, и требуется выяснить, где в ней в качестве подстроки может встречаться строка $s$. Формально нужно найти все позиции $i$, такие, что существует такой шифр подстановки, что $t_i \dots t_{i + |s| – 1}$ представляет собой зашифрованную версию $s$.
Формат ввода
Первая строка входного файла содержит $t$. Вторая строка входного файла содержит $s$. Каждая строка состоит из символов с ASCII-кодами от 33 до 126. Известно, что $1 \le |s| \le |t| \le 200\,000$.
Формат вывода
Первая строка выходного файла должна содержать $k$ — количество потенциальных вхождений $s$ в $t$. Вторая строка должна содержать $k$ целых чисел в порядке возрастания — позиции потенциальных вхождений. Позиции в строке нумеруются, начиная с 1.
Примечание
Первый тест соответствует подстановочному шифру из условия.
Во втором тесте есть два потенциальных вхождения $s$ в $t$ — «tat» $\to$ «aba», «tat» $\to$ «bab».
Ограничения
Ограничение времени
1 с
Ограничение памяти
256 МБ
Пример 1
bwca
love
1
1
Пример 2
abab
tat
2
1 2