| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 5 초 | 1024 MB | 15 | 3 | 3 | 37.500% |
3019 год. При раскопках древнего города Иннополис археологи обнаружили артефакт --- жёсткий диск, на котором находится файл, предположительно содержащий тексты всех задач всероссийских олимпиад по информатике.
После исследования файла было выяснено, что информация в нём закодирована таким образом, что записанный в файле текст представляет собой строку $t$ из букв английского алфавита. Текст с задачами оказался довольно длинным и содержал много повторений, поэтому файл хранился на диске в сжатом виде. Для его распаковки используется следующий алгоритм.
В процессе распаковки формируется строка $t$ из строчных букв английского алфавита. Исходно строка пуста. Сжатый файл состоит из $n$ блоков, которые должны быть обработаны в порядке следования. Каждый блок имеет один из двух типов.
1 $w$>>, где $w$ --- строка. При обработке такого блока в конец строки $t$ дописывается строка $w$.2 $pos$ $len$>>, где $pos$ и $len$ --- положительные целые числа. Пусть символы строки $t$ пронумерованы с 1ドル$. При обработке такого блока в конец строки $t$ по очереди приписываются $len$ подряд идущих символов строки $t,ドル начиная с позиции $pos$. При этом, если значение $len$ достаточно велико, некоторые только что выписанные символы могут быть снова использованы при обработке того же блока.Ученые решили выяснить, сколько раз некоторая идея встречалась в олимпиадах. Для этого они сформировали строку $p$ из строчных букв английского алфавита и хотят найти количество вхождений строки $p$ как подстроки в полученную после распаковки файла строку $t$.
Строка $p$ длины $m$ входит в строку $t$ как подстрока с позиции $i,ドル если $m$ следующих подряд символов строки $t,ドル начиная с $i$-го, представляют собой строку $p$. Например, строка <<aba>> входит как подстрока в строку <<ababaaba>> три раза: с позиций 1, 3 и 6.
Требуется написать программу, которая определяет количество вхождений заданной строки $p$ в полученную после распаковки файла строку $t$.
В первой строке находятся натуральные числа $m$ и $n$ --- длина строки $p$ и количество блоков в сжатом тексте (1ドル \le m \le 2 \cdot 10^5,ドル 1ドル \le n \le 10^4$).
Во второй строке входных данных задана непустая строка $p,ドル состоящая из строчных букв английского алфавита.
В следующих $n$ строках находятся описания блоков в описанном в условии формате. Для блоков первого типа приписываемая строка $w$ непуста, сумма длин всех строк $w$ в блоках первого типа не превышает 2ドル \cdot 10^5$. Для блоков второго типа в строке $t$ к моменту обработки этого блока находится не менее $pos$ символов. Длина распакованного текста не превышает 10ドル^{15}$ символов.
Выведите одно целое число --- количество вхождений строки $p$ в текст.
Обозначим длину текста $t$ после обработки $i$ блоков как $L_i$.
Обозначим тип $i$-го блока как $type_i$. Если $type_i = 2,ドル то обозначим параметры этого блока как $pos_i$ и $len_i$.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 6 | $m \le 2,000円,ドル $n = 1,ドル $L_n \le 1,000円$ |
| 2 | 10 | $m \le 10^5,ドル $n \le 2,000円,ドル $L_n \le 10^{6}$ |
| 3 | 10 | $m \le 2,000円,ドル $n \le 2,000円,ドル $L_n \le 10^{10},ドル кроме первого блока, $type_i=2,ドル $pos_i=1,ドル $len_i$ делится на $L_1$ |
| 4 | 10 | $m \le 2,000円,ドル $n \le 2,000円,ドル $L_n \le 10^{10},ドル $pos_i = L_{i-1}$ |
| 5 | 10 | $m \le 20,ドル $n \le 2,000円,ドル $L_n \le 10^{10},ドル $pos_i=1, len_i \le 10^7$ |
| 6 | 4 | $m \le 2,000円,ドル $n \le 2,000円,ドル $L_n \le 10^{10},ドル $pos_i=1, len_i \le 10^7$ |
| 7 | 10 | $m \le 20,ドル $n \le 20,ドル $L_n \le 10^{10},ドル $p$ состоит из букв |
| 8 | 6 | $m \le 20,ドル $n \le 20,ドル $L_n \le 10^{10},ドル $pos_i + len_i - 1 \le L_{i-1}$ |
| 9 | 2 | $m = 1,ドル $n \le 2,000円,ドル $L_n \le 10^{10},ドル $p$ состоит из букв |
| 10 | 4 | $m \le 20,ドル $n \le 2,000円,ドル $L_n \le 10^{10},ドル $p$ состоит из букв |
| 11 | 5 | $m \le 20,ドル $n \le 2,000円,ドル $L_n \le 10^{10}$ |
| 12 | 14 | $m \le 10^5,ドル $n \le 2,000円,ドル $L_n \le 10^{10}$ |
| 13 | 9 | $m \le 2 \cdot 10^5,ドル $n \le 10,000円,ドル $L_n \le 10^{15}$ |
3 4 aba 1 ab 2 1 3 2 3 3 2 1 8
6
При распаковке файла в примере последовательно получаются следующие строки:
<<>> $\to$ <<ab>> $\to$ <<ababa>> $\to$ <<ababaaba>> $\to$ <<ababaabaababaaba>>.
Строка <<aba>> входит как подстрока в результирующую строку <<ababaabaababaaba>> 6ドル$ раз.