Курс: Строки

Модуль: Префикс-функция, Z-функция

Задачи

Задача

5/10

Z-функция

Ограничение по времени: 2000 ms
Ограничение по памяти: 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Теория

Z-функция от строки S - массив Z, каждый элемент которого Z[i] равен длиннейшему префиксу подстроки, начинающейся с позиции i в строке S, который одновременно является и префиксом всей строки S. Значение Z-функции в нулевой позиции обычно равно или нулю, или длине всей строки. Сложность: O(|S| ^ 2) или O(|S|).
 
Префикс-функция от строки S - массив P, каждый элемент которого P[i] равен длиннейшему суффиксу подстроки, начинающейся с позиции i в строке S, который одновременно является и суффиксом всей строки S. Значение P-функции в нулевой позиции обычно равно или нулю, или длине всей строки. Сложность: O(|S| ^ 2) или O(|S|).
 
Попробуйте сами реализовать Z и префикс функции за O(|S| ^ 2).

Задача

Даны две строки - S и T. Ваша задача по запросам вывести колличество вхождений i-того префикса строки S в строку T.

Входные данные
В первой строке вводится k - колличество запросов (\(k <= длина( S)\)), строка S и строка T. Далее вводится k запросов, запрос на количество вхождений i-того префикса строки S в стркоу T.

Выходные данные
Вывести k строк с ответами на запросы.
 

 

Примеры
Входные данные Выходные данные
1
2 ali balimali
3
0
2
8