#P5599. 【XR-4】文本编辑器

【XR-4】文本编辑器

题目背景

赛时提醒:本题输入数据是 Windows 格式,而非 Linux 格式,所以在每一行末尾的 \n 之前有一个多余的 \r 字符。请使用 scanfcin 读入数据,而非 getline,因为后者会多读入一个 \r

题目描述

小 X 在制作一个文本编辑器,现在需要实现最基本的“查找和替换”功能。

在文本编辑器中,文件是以一个长度为 nn 的字符串 aa 的形式存储的。

同时,用户拥有一个包含 mm单词的字典,每个单词都是一个字符串,称第 ii 个单词为 sis_i

接下来定义查找和替换功能:

  • 查找功能:有两个参数 l,rl, r,表示询问对于字典中的每个单词 sis_ia[l:r]a[l : r]sis_i 的出现次数之和。
    即询问 $\displaystyle \sum_{i=1}^{m} \mathrm{occur}(s_i, a[l : r])$,其中 occur(s,t)\mathrm{occur}(s, t) 表示字符串 ss 在字符串 tt 中的出现次数。

  • 替换功能:有三个参数 l,r,tl, r, t,其中 tt 是一个字符串,表示将 a[l:r]a[l : r] 替换为 tt 不断重复的结果。
    即如果把 Mds72SKsLL\texttt{Mds72SKsLL} 替换为 Rabb\texttt{Rabb} 不断重复的结果,则原字符串变为 RabbRabbRa\texttt{RabbRabbRa}

用户给出了 qq 个操作,每个操作是查找替换之一,你需要正确回答每个查找操作的答案。

输入格式

第一行三个整数 n,m,qn, m, q,依次表示文件 aa 的长度,字典中的单词数,询问的个数。

第二行一个长度为 nn 的字符串 aa,表示初始文件。

接下来 mm 行,第 ii 行一个字符串,表示第 ii 个单词 sis_i

接下来 qq 行,每行表示一个操作:
每行的第一个数 op\mathrm{op} 表示此次操作的类型;
op=1\mathrm{op} = 1,则接下来两个整数 l,rl, r,表示这是一次查找操作,参数为 l,rl, r
op=2\mathrm{op} = 2,则接下来两个整数 l,rl, r 和一个字符串 tt,表示这是一次替换操作,参数为 l,r,tl, r, t

输出格式

对于每个查找操作,一行一个整数,表示本次查找操作的答案。

6 2 5
BBABBA
BB
BAB
1 1 6
2 3 5 A
1 2 3
2 1 6 B
1 1 5

3
0
4

提示

本题采用捆绑测试。

  • Subtask 1(7 points):n,m,q50n, m, q \le 50,所有字符串长度 50\le 50,时限 1s1\text{s}
  • Subtask 2(7 points):n,q3000n, q \le 3000,时限 1s1\text{s}
  • Subtask 3(13 points):m=1m = 1,时限 2s2\text{s}
  • Subtask 4(17 points):没有替换操作,即 op=1\mathrm{op} = 1,时限 2s2\text{s}
  • Subtask 5(18 points):n,q8×104n, q \le 8 \times 10^4si50\displaystyle \sum |s_i| \le 50t8×104\displaystyle \sum |t| \le 8 \times 10^4,时限 1s1\text{s}
  • Subtask 6(13 points):n,q5×104n, q \le 5\times 10^4si5×104\displaystyle \sum |s_i| \le 5\times 10^4t5×104\displaystyle \sum |t| \le 5\times 10^4,时限 1s1\text{s}
  • Subtask 7(25 points):无特殊限制,时限 2s2\text{s}

对于 100%100\% 的数据:
n,m,q,l,r,opn, m, q, l, r, \mathrm{op} 的限制:1lrn1061 \le l \le r \le n \le 10^61m,q1051 \le m, q \le 10^5op{1,2}\mathrm{op} \in \{ 1, 2 \}
对字符串长度的限制:si50|s_i| \le 50si2×105\displaystyle \sum |s_i| \le 2 \times 10^5t106\displaystyle \sum |t| \le 10^6
所有字符串保证不为空串,且出现的字符属于集合 Σ\mathbf{\Sigma},其中 $\mathbf{\Sigma} = [\texttt a, \texttt z] \cup [\texttt A, \texttt Z] \cup [\texttt 0, \texttt 9]$,即所有大小写英文字母以及数字,故 Σ=62|\mathbf{\Sigma}| = 62

需要特别注意的是,与文件相比,单词的长度是非常小的。在解题时你可能需要利用这一点。


【一些定义】

对于一个长度为 len\mathrm{len} 的字符串 ss,符号 s[l:r]s[l : r]1lrlen1 \le l \le r \le \mathrm{len})表示 ss 中从 llrr子串。即 ss 中从第 ll 个字符到第 rr 个字符(包含端点)连续拼接在一起形成的字符串。
对于一个字符串 ss,符号 s|s| 表示它的长度。