#3194. 「ROI 2019 Day2」模式串查找

内存限制:1024 MiB 时间限制:5000 ms 标准输入输出
题目类型:传统 评测方式:Special Judge
上传者: Planet6174

题目描述

译自 ROI 2019 Day2 T4. Поиск идеи

给出模式串 p ,其长度为 m 。又给出「压缩后的」文本串 t ,试求 p t 中出现的次数。两个字符串均只包含小写英文字母。

压缩后的 t 分为 n 个有顺序的块。块的类型及解压方式如下:

  • 开始解压时 t 为空串。
  • \tt1\it\ w ,其中 w 是一个字符串。在解压过程中,当读取到这一块时,将 w 放在 t 的末尾。
  • \tt2\rm\ pos\ len ,将 t_{\rm pos} 复制到 t 的末尾,再将 t_{\mathrm{pos}+1} 复制到 t 的末尾……共复制 \rm len 个字符。比如,如果 t=\tt aba ,当前块为 2\ 1\ 7 ,则 t 会变为 \tt abaabaabaa

输入格式

m,n
p
接下来 n 行,每行一个块

样例

样例输入

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

样例输出

6

样例说明

开始:空串
读取第一块后: \tt ab
读取第二块后: \tt ababa
读取第三块后: \tt ababaaba
读取第四块后: \tt ababaabaababaaba

\tt ababaabaababaaba\\aba\ \ aba\ \ aba\ \ \ \\\ \ aba\ \ \ aba\ \ aba

数据范围与提示

L_i 表示读取第 i 块后 t 的长度。 如果第 i 个块属于第二类块,我们用 \mathrm{pos}_i \mathrm{len}_i 特指这个块的 \rm pos \rm len

子任务 # 分值 m⩽ n⩽ L_n⩽ 额外条件
1 6 \color{#068}{2000} \color{#000}{=1} \color{#068}{1000}
2 10 \color{#0a5}{10^5} \color{#068}{2000} \color{#960}{10^6}
3 10 \color{#068}{2000} \color{#a50}{10^{10}} 对于任意一个第二类块,
\mathrm{pos}_i=1 \mathrm{len}_i L_1 的因数
4 10 \mathrm{pos}_i = L_{i−1}
5 10 \color{#000}{20} \mathrm{pos}_i=1, \mathrm{len}_i⩽10^7
6 4 \color{#068}{2000}
7 10 \color{#000}{20} \color{#000}{20} 文本串里只包含 \tt a
\mathrm{pos}_i+\mathrm{len}i-1⩽L_{i–1}
8 6 \mathrm{pos}_i+\mathrm{len}_i-1⩽L_{i–1}
9 2 \color{#000}{=1} \color{#068}{2000} 文本串里只包含 \tt a
10 4 \color{#000}{20}
11 5
12 14 \color{#0a5}{10^5}
13 9 \color{#790}{2×10^5} \color{#085}{10^4} \color{#e30}{10^{15}}

对于所有子任务,保证 \sum |w_i|\le 2\times 10^5