#2252. Поиск идеи

    ID: 2252 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>TEAM赛事:contest3434来源:qoj.ac数据:公开样例字符串枚举

Поиск идеи

Поиск идеи

题目描述

XXXI Всероссийская олимпиада школьников по информатике, заключительный этап, второй тур Иннополис, 15 апреля 2019 года Задача 8. Поиск идеи Ограничение по времени: 5 секунд Ограничение по памяти: 1024 мегабайта 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 ⩽m ⩽2 · 105, 1 ⩽n ⩽104). Во второй строке входных данных задана непустая строка p, состоящая из строчных букв ан- глийского алфавита. В следующих n строках находятся описания блоков в описанном в условии формате. Для блоков первого типа приписываемая строка w непуста, сумма длин всех строк w в блоках первого типа не превышает 2 · 105. Для блоков второго типа в строке t к моменту обработки этого блока находится не менее pos символов. Длина распакованного текста не превышает 1015 символов. Формат выходных данных Выведите одно целое число — количество вхождений строки p в текст. Пример стандартный ввод стандартный вывод 3 4 6 aba 1 ab 2 1 3 2 3 3 2 1 8 Страница 7 из 8 XXXI Всероссийская олимпиада школьников по информатике, заключительный этап, второй тур Иннополис, 15 апреля 2019 года Пояснение к примеру При распаковке файла в примере последовательно получаются следующие строки: «» →«ab» →«ababa» →«ababaaba» →«ababaabaababaaba». Строка «aba» входит как подстрока в результирующую строку «ababaabaababaaba» 6 раз. Система оценки Обозначим длину текста t после обработки i блоков как Li. Обозначим тип i-го блока как typei. Если typei = 2, то обозначим параметры этого блока как posi и leni. Ограничения Результаты Необх. Подз. Баллы во время тура подзадачи m, n Ln дополнительно m ⩽2 000 Ln ⩽1 000 1 6 — первая ошибка n = 1 m ⩽105 Ln ⩽106 2 10 У, 1 первая ошибка n ⩽2 000 кроме первого блока m ⩽2 000 Ln ⩽1010 3 10 typei = 2, posi = 1 1 первая ошибка n ⩽2 000 leni делится на L1 m ⩽2 000 Ln ⩽1010 4 10 posi = Li−1 1 первая ошибка n ⩽2 000 m ⩽20 Ln ⩽1010 posi = 1, leni ⩽107 5 10 — первая ошибка n ⩽2 000 m ⩽2 000 Ln ⩽1010 posi = 1, leni ⩽107 6 4 1, 5 первая ошибка n ⩽2 000 m ⩽20 p состоит из букв «a» Ln ⩽1010 7 10 — первая ошибка n ⩽20 posi + leni −1 ⩽Li−1 m ⩽20 Ln ⩽1010 posi + leni −1 ⩽Li−1 8 6 7 первая ошибка n ⩽20 m = 1 Ln ⩽1010 9 2 p состоит из букв «a» — первая ошибка n ⩽2 000 m ⩽20 Ln ⩽1010 10 4 p состоит из букв «a» 7–9 первая ошибка n ⩽2 000 m ⩽20 Ln ⩽1010 11 5 У, 5, 7–10 первая ошибка n ⩽2 000 m ⩽105 Ln ⩽1010 12 14 У, 1–11 первая ошибка n ⩽2 000 m ⩽2 · 105 Ln ⩽1015 13 9 У, 1–12 первая ошибка n ⩽10 000 Страница 8 из 8

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

3 4
aba
1 ab
2 1 3
2 3 3
2 1 8
6