| Автор: | А. Баранов | Ограничение времени: | 1 сек | |
| Входной файл: | input.txt | Ограничение памяти: | 2 Мб | |
| Выходной файл: | output.txt |
Пусть имеется текстовая строка S, состоящая из произвольных печатных символов (ASCII 32-126). Требуется определить общее число ее подстрок, совпадающих с некоторым заданным образцом T.
Для решения задачи следует воспользоваться алгоритмом Кнута-Морриса-Пратта.
В заголовке входного файла "input.txt" содержится строка T, выступающая в роли образца. Далее следует строка S, в которой необходимо выполнить поиск.
Выходной файл "output.txt" должен содержать число найденных подстрок.
0 < |T| ≤ 5 ⋅ 104, 0 ≤ |S| ≤ 2 ⋅ 107
| № | Входной файл (input.txt) |
Выходной файл (output.txt) |
|---|---|---|
| 1 |
|
|
| 2 |
|
|