P5599 [XR-4] Text Editor

**Reminder during the contest: The input for this problem uses Windows line endings, not Linux line endings, so there is an extra `\r` character before `\n` at the end of each line. Please use `scanf` or `cin` to read the input, rather than `getline`, because the latter will read an extra `\r`.**

Little X is building a text editor and now needs to implement the most basic “**find and replace**” feature. In the text editor, the file is stored as a string $a$ of length $n$. Meanwhile, the user has a dictionary containing $m$ **words**. Each word is a string, and the $i$-th word is denoted by $s_i$. Next, define the **find and replace** feature: - **Find**: There are two parameters $l, r$, asking for the sum, over every **word** $s_i$ in the dictionary, of the number of occurrences of $s_i$ in $a[l : r]$. That is, compute $\displaystyle \sum_{i=1}^{m} \mathrm{occur}(s_i, a[l : r])$, where $\mathrm{occur}(s, t)$ denotes the number of occurrences of string $s$ in string $t$. - **Replace**: There are three parameters $l, r, t$, where $t$ is a string, meaning to replace $a[l : r]$ with the result of repeating $t$ endlessly and taking the needed prefix. For example, if we replace $\texttt{Mds72SKsLL}$ with the endlessly repeated string $\texttt{Rabb}$, then the original string becomes $\texttt{RabbRabbRa}$. The user provides $q$ operations, each being either **find** or **replace**. You need to output the correct answer for every **find** operation.

The first line contains three integers $n, m, q$, representing the length of the file $a$, the number of words in the dictionary, and the number of queries. The second line contains a string $a$ of length $n$, representing the initial file. The next $m$ lines each contain a string; the $i$-th line is the $i$-th word $s_i$. The next $q$ lines each describe an operation: The first number on each line is $\mathrm{op}$, indicating the type of operation. If $\mathrm{op} = 1$, then two integers $l, r$ follow, meaning this is a **find** operation with parameters $l, r$. If $\mathrm{op} = 2$, then two integers $l, r$ and a string $t$ follow, meaning this is a **replace** operation with parameters $l, r, t$.

For each **find** operation, output one integer per line, representing the answer to this find query.

**This problem uses bundled testdata.** - Subtask 1 (7 points): $n, m, q \le 50$, all string lengths $\le 50$, time limit $1\text{s}$. - Subtask 2 (7 points): $n, q \le 3000$, time limit $1\text{s}$. - Subtask 3 (13 points): $m = 1$, time limit $2\text{s}$. - Subtask 4 (17 points): There are no **replace** operations, i.e. $\mathrm{op} = 1$, time limit $2\text{s}$. - Subtask 5 (18 points): $n, q \le 8 \times 10^4$, $\displaystyle \sum |s_i| \le 50$, $\displaystyle \sum |t| \le 8 \times 10^4$, time limit $1\text{s}$. - Subtask 6 (13 points): $n, q \le 5\times 10^4$, $\displaystyle \sum |s_i| \le 5\times 10^4$, $\displaystyle \sum |t| \le 5\times 10^4$, time limit $1\text{s}$. - Subtask 7 (25 points): No special constraints, time limit $2\text{s}$. For $100\%$ of the data: Constraints on $n, m, q, l, r, \mathrm{op}$: $1 \le l \le r \le n \le 10^6$, $1 \le m, q \le 10^5$, $\mathrm{op} \in \{ 1, 2 \}$. Constraints on string lengths: $|s_i| \le 50$, $\displaystyle \sum |s_i| \le 2 \times 10^5$, $\displaystyle \sum |t| \le 10^6$. All strings are guaranteed to be non-empty, and all characters belong to the set $\mathbf{\Sigma}$, where $\mathbf{\Sigma} = [\texttt a, \texttt z] \cup [\texttt A, \texttt Z] \cup [\texttt 0, \texttt 9]$, i.e. all lowercase letters, uppercase letters, and digits, so $|\mathbf{\Sigma}| = 62$. **A special note: Compared to the file, the words are very short. You may need to make use of this when solving the problem.** ---- **[Some definitions]** For a string $s$ of length $\mathrm{len}$, the notation $s[l : r]$ ($1 \le l \le r \le \mathrm{len}$) denotes the **substring** of $s$ from $l$ to $r$. That is, the string formed by concatenating the $l$-th through the $r$-th characters of $s (inclusive) in order. For a string $s$, the notation $|s|$ denotes its length. Translated by ChatGPT 5