Избрав путь политика и полководца, Цезарь имел немного времени для творческой работы, однако написал сочинения разных жанров: эпическую поэму "Геркулес", трагедию "Царь Эдип", поэму "Путешествие", "Записки о галльской войне" и "Записки о гражданской войне". Были изданы сборники его сентенций, речей, писем. Кроме того, великий полководец интересовался филологией.
Отвлекшись от написания поэмы, Цезарь записал одну под другой две строчки и задумался. Затем он посмотрел на написанные строчки и понял, что первая строка (S) может содержать в себе несколько раз вторую строку (T). Гай Юлий Цезарь решил подсчитать все вхождения строки T в строку S. Помогите ему, напишите соответствующую программу.
Входные данные
Первые две строки входных данных содержат строки
S и
T, соответственно. Длины строк больше 0 и меньше 50000, строки содержат только строчные латинские буквы.
Выходные данные
Выведите номера символов, начиная с которых строка
T входит в строку
S, в порядке возрастания (по одному значению в строке).
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
ababbababa
aba |
0
5
7 |