Задача №113281. Подстрока подстроки
Мальчик Вася очень любит слушать радио. На выходных наш герой уехал за город с родителями и пропустил несколько важных передач. У Васи есть запись за весь день. Про каждую передачу он знает, что она продолжалась во время от l i до r i и то, что в ней определённое количество раз должно встречаться нужное слово (для разных передач слова, возможно, разные). К сожалению, бывает так, что передачу отменяют и заменяют на другую. Естественно, Вася не хочет слушать зря ненужную информацию, поэтому он обратился за помощью к вам. Для каждого отрезка записи он хочет знать, сколько раз в нём встречается нужное слово.
Все строки во входном файле состоят из строчных латинских букв. Все числа целые.
Первая строка входного файла содержит два числа: f и N .
Число f может принимать два значения: 0 или 1 . Значение f = 0 означает, что на запросы требуется отвечать в режиме offline, в противном случае требуется работать в режиме online.
N — число запросов на которые требуется ответить.
Во второй строке входного файла содержится текст передачи — строка s , в подстроках которой надо искать строки-запросы.
В случае f = 0 , следующие 2 N строк содержат описание запросов. В первой строке описания i -го запроса содержится строка-запрос t i . Вторая строка описания запроса содержит целые числа l i и r i . Ответом на запрос с номером i является число вхождений строки t i в подстроку s l i s l i + 1 ... s r i - 1 s r i .
Если же
f
= 1
, третья строка входного файла содержит целое число
x
, которое будет использовано для генерации запросов. Следующие
2
N
строк содержат описание запросов. В первой строке описания
i
-го запроса содержится закодированная строка-запрос
. Декодированная строка-запрос может быть получена следующим образом: сопоставим символам 'a', 'b', ..., 'z' числа
0, 1, ..., 25
соответственно. Тогда коды символов для строк
и
t
i
связаны следующим соотношением:
. Вторая строка описания запроса содержит целые числа
и
. Истинные значения чисел
l
i
и
r
i
могут быть вычислены по формулам:
,
, где
L
— длина строки
s
. Для очередного запроса значения
x
меняется по следующему правилу:
x
= (
x
+
a
i
)
mod
12345
, где
a
i
— ответ на
i
-ый запрос.
В выходной файл требуется вывести N строк, в i -ой строке должно содержатся единственное целое число — ответ на i -ый запрос.
Данная задача имеет 3 подзадачи:
-
f
= 0
,
1 ≤ |
s
| ≤ 1 000
. Суммарная длина строк-запросов не превосходит
100 000
.
Подзадача оценивается в 20 баллов.
-
f
= 0
,
1 ≤ |
s
| ≤ 7 500
. Суммарная длина строк-запросов не превосходит
150 000
.
Подзадача оценивается в 30 баллов.
-
f
= 1
,
1 ≤ |
s
| ≤ 20 000
. Суммарная длина запросов не превосходит
150 000
.
Подзадача оценивается в 50 баллов.
0 3 buyourbotvaonlytodayourjuryisthebestjury democracy 1 40 botva 4 11 our 1 40
0 1 2
1 3 buyourbotvaonlytodayourjuryisthebestjury 21 ijrthwfhd 21 19 gtyaf 24 31 syv 20 18
0 1 2