#P15806. [中国国家队2025年林芝集训]唐唐题

    ID: 15017 传统题 5000ms 1024MiB 尝试: 1 已通过: 1 难度: 10 上传者: 标签>字符串KMP算法基础倍增数据结构CF3300

[中国国家队2025年林芝集训]唐唐题

题目描述

三〇一九年,考古学家在古城市 Innopolis 进行挖掘时,发现了一件古代遗物——一个硬盘。硬盘中有一个文件,据推测,其中保存了所有 ROI 题目的文本。

研究发现,文件内容被编码成一个由小写英文字母组成的字符串 tt。由于题目文本很长,并且有许多重复内容,所以文件以压缩形式存储。

解压缩过程如下。

初始时,字符串 tt 为空。压缩文件包含 nn 个块,按顺序处理。每个块有以下两种类型之一:

  • 1 w:其中 ww 是一个字符串。处理该块时,将字符串 ww 追加到 tt 的末尾。
  • 2 pos len:其中 pospos 和 lenlen 是正整数。假设当前字符串 tt 的字符从 11 开始编号。处理该块时,将 tt 中从位置 pospos 开始的连续 lenlen 个字符依次追加到 tt 的末尾。若 lenlen 足够大,则本次刚追加的字符也可能在处理同一块时继续被使用。

考古学家想统计某个算法在 ROI 中被考察的次数。为此,他们给定一个由小写英文字母组成的模式串 pp,并希望求出 pp 在最终解压出的字符串 tt 中作为子串出现的次数。

若长度为 mm 的字符串 pp 从 tt 的位置 ii 开始出现,则 ti,ti+1,…,ti+m−1t_i,t_{i+1},\ldots,t_{i+m-1} 与 pp 完全相同。出现位置可以重叠。

请输出 pp 在解压缩后的字符串 tt 中出现的次数。

输入格式

第一行包含两个自然数 m,nm,n,分别表示模式串 pp 的长度和压缩文本中的块数。

第二行包含一个非空字符串 pp,仅由小写英文字母组成。

接下来 nn 行,每行描述一个块,格式为题目描述中的 1 w 或 2 pos len。

输出格式

输出一个整数,表示字符串 pp 在解压缩后文本 tt 中出现的次数。

样例一

输入

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

输出

6

解释

解压缩过程为:

$$\text{ab}\to \text{ababa}\to \text{ababaaba}\to \text{ababaabaababaaba}.$$

aba 在 ababaabaababaaba 中出现了 66 次。

样例二

输入

16 15
ilovethisproblem
1 ilovethisproblem
2 1 16
2 1 32
2 1 64
2 1 128
2 1 256
2 1 512
2 1 1024
2 1 2048
2 1 4096
2 1 8192
2 1 16384
2 1 32768
2 1 65536
2 1 131072

输出

16384

样例三

输入

20 10
aaaaaaaaaaaaaaaaaaaa
1 aaaaaaaaaaaaaaaaaaaamusoraaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaamnogomusoraaaaaaaaaaaaaaaaaaaaa
2 19 1
2 18 2
2 17 3
2 16 4
2 15 5
2 14 6
2 13 7
2 12 8
2 11 9

输出

69

样例四

见原题附件。

数据范围与子任务

设将前 ii 块解压缩后字符串的长度为 LiL_i,第 ii 块的类型为 typeitype_i。

子任务 分值 m≤m\le n≤n\le Ln≤L_n\le 其它特殊性质
1 6 2000 1 1000 -
2 10 10510^5 2000 10610^6
3 2000 101010^{10} 对所有 i>1i>1,typei=2,posi=1,L1∣lenitype_i=2,pos_i=1,L_1\mid len_i
4 posi=Li−1pos_i=L_{i-1}
5 20 posi=1,leni≤107pos_i=1,len_i\le 10^7
6 4 2000
7 10 20 pp 只含字母 a,且 posi+leni−1≤Li−1pos_i+len_i-1\le L_{i-1}
8 6 posi+leni−1≤Li−1pos_i+len_i-1\le L_{i-1}
9 2 1 2000 pp 只含字母 a
10 4 20
11 5 -
12 14 10510^5
13 9 2×1052\times 10^5 10000 101510^{15}

对于 100%100\% 的数据,保证

∑∣w∣≤2×105,\sum |w|\le 2\times 10^5,

其中求和只对所有类型为 1 w 的块中的字符串 ww 计算。