题目描述
译自 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$ 行，每行一个块
样例
input
3 4
aba
1 ab
2 1 3
2 3 3
2 1 8output
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{#068}{2000}$ | $\color{#a50}{10^{10}}$ | 对于任意一个第二类块， $\mathrm{pos}_i=1$，$\mathrm{len}_i$ 是 $L_1$ 的因数 |
| 4 | 10 | $\color{#068}{2000}$ | $\color{#068}{2000}$ | $\color{#a50}{10^{10}}$ | $\mathrm{pos}i = L{i−1}$ |
| 5 | 10$ $ | $\color{#000}{20}$ | $\color{#068}{2000}$ | $\color{#a50}{10^{10}}$ | $\mathrm{pos}_i=1, \mathrm{len}_i⩽10^7$ |
| 6 | 4 | $\color{#068}{2000}$ | $\color{#068}{2000}$ | $\color{#a50}{10^{10}}$ | $\mathrm{pos}_i=1, \mathrm{len}_i⩽10^7$ |
| 7 | 10 | $\color{#000}{20}$ | $\color{#000}{20} $ | $\color{#a50}{10^{10}}$ | 文本串里只包含 $\tt a$ $\mathrm{pos}i+\mathrm{len}i-1⩽L{i–1}$ |
| 8 | 6 | $\color{#000}{20}$ | $\color{#000}{20} $ | $\color{#a50}{10^{10}}$ | $\mathrm{pos}_i+\mathrm{len}i-1⩽L{i–1}$ |
| 9 | 2 | $\color{#000}{=1}$ | $\color{#068}{2000}$ | $\color{#a50}{10^{10}}$ | 文本串里只包含 $\tt a$ |
| 10 | 4 | $\color{#000}{20}$ | $\color{#068}{2000}$ | $\color{#a50}{10^{10}}$ | 文本串里只包含 $\tt a$ |
| 11 | 5 | $\color{#000}{20}$ | $\color{#068}{2000}$ | $\color{#a50}{10^{10}}$ | |
| 12 | 14 | $\color{#0a5}{10^5}$ | $\color{#068}{2000}$ | $\color{#a50}{10^{10}}$ | |
| 13 | 9 | $\color{#790}{2×10^5}$ | $\color{#085}{10^4}$ | $\color{#e30}{10^{15}}$ |
对于所有子任务，保证 $\sum |w_i|\le 2\times 10^5$。