Задачи
Иголка в стоге сена
Иголка в стоге сена
Напишите программу, которая находит все совпадения заданного шаблона со входной строкой. Эта задача напоминает поиск иголки в стоге сена. Программа должна найти все местоположения иголки в стоге сена.
\InputFile
Состоит из нескольких тестов. Каждый тест состоит из трех строк, содержащих:
\begin{itemize}
\item длину иголки,
\item саму иголку,
\item стог сена.
\end{itemize}
Длина иголки не более \textbf{10000} символов. Стог сена не будем ограничивать в размерах - ваша программа должна читать его по мере обработки.
Тесты следуют один за другим, каждый занимает ровно три строки без разделителей.
\OutputFile
Для каждого теста следует вывести все позиции вхождения иголки в стог сена. Если найдено совпадение, то результат должен содержать положение первого символа совпадения. Символы в стоге сена нумеруются с нуля.
Для каждого теста позиции совпадения следует отсортировать в порядке возрастания и вывести каждую из них в отдельной строке. Для двух различных тестов позиции совпадения должны быть разделены пустой строкой.
Входные данные #1
2 na banananobano 6 foobar foo 9 foobarfoo barfoobarfoobarfoobarfoobarfoo
Выходные данные #1
2 4 3 9 15 21
Объяснение: Обратите внимание на двойную пустую строку в выходном файле, так как не было найдено совпадение для второго теста