시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
5 초 | 1024 MB | 4 | 1 | 1 | 25.000% |
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$ раз.