EduBrick

E. Две ошибки

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

Найдите все вхождения pp в tt, где разрешено не совпасть не более чем в двух символах.

Приём из класса - две Z-функции - тут не работает: он покрывает окно ровно с двух концов, а при двух ошибках между ними остаётся кусок, про который ничего не известно.

Формат ввода

Первая строка содержит pp, вторая - tt (1≤∣p∣,∣t∣≤1051 \le \lvert p \rvert, \lvert t \rvert \le 10^5).

Строки состоят из строчных латинских букв.

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

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

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

Примеры

ввод
abc
abcxbcaxc
вывод
3
1 4 7
ввод
ab
a
вывод
0

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