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


Задача

5 /10


Z-функция

Теория Нажмите, чтобы прочитать/скрыть

Z-функция
Z-функция от строки S - массив Z, каждый элемент которого Z[i] равен длиннейшему префиксу подстроки, начинающейся с позиции i в строке S, который одновременно является и префиксом всей строки Z. Значение 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

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

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w6421
Комментарий учителя

Напишите программу

или выберите язык программирования и введите исходный код

Auto

       

Результат проверки программы 
Для проверки решения задачи необходимо зарегистрироваться или авторизоваться!