Алгоритмы и структуры данных

Поиск подстроки

Дан длинный текст t и строка s. Необходимо найти все вхождения строки s в тексте t. Другими словами, нужно определить все начальные позиции в t, где s полностью совпадает с соответствующим фрагментом текста.

Входные данные

Первая строка входных данных содержит текст t (1 ≤ |t| ≤ ).
Вторая строка содержит строку s (1 ≤ |s| ≤ |t|).

Выходные данные

Выведите в одну строку все начальные позиции в t, в которых встречается s. Позиции должны идти в порядке возрастания (от начала текста к концу) и отделяться пробелом. Индексация начинается с 0.

Примеры

Ввод
Вывод
habababohabo ba
2 4
barfoobarfoobarfoobarfoobarfoo foobarfoo
3 9 15 21

Пояснение

  1. В тексте habababohabo строка ba обнаруживается в следующих местах: habababohabo → habababohabo, habababohabo
  1. В тексте barfoobarfoobarfoobarfoobarfoo строка foobarfoo обнаруживается в следующих местах: barfoobarfoobarfoobarfoobarfoo, barfoobarfoobarfoobarfoobarfoobarfoo, barfoobarfoobarfoobarfoobarfoobarfoo, barfoobarfoobarfoobarfoobarfoo
 

Constraints

Time limit: 5 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue