#PU1281. USACO 2023 January Contest, Gold — Problem 1. Find and Replace
USACO 2023 January Contest, Gold — Problem 1. Find and Replace
USACO 2023 January Contest, Gold — Problem 1. Find and Replace
题目描述
Bessie is using the latest and greatest innovation in text-editing software, miV! Its powerful find-and-replace feature allows her to find all occurrences of a lowercase English letter and replace each with a nonempty string of lowercase letters . For example, given the string "", if Bessie selects to be 'l' and to be "", the given string transforms into "". Bessie starts with the string "" and transforms it using a number of these find-and-replace operations, resulting in a final string . Since could be massive, she wants to know, given and with , what (the substring of from the -th to the -th character inclusive) is. It is guaranteed that the sum of over all operations is at most , and that .
输入格式
The first line contains , , and the number of operations. Each subsequent line describes one operation and contains and for that operation. All characters are in the range 'a' through 'z'.
输出格式
(见题面原文)
数据范围
Inputs 2-7: Inputs 8-15: No additional constraints. Problem credits: Benjamin Qi
样例
样例 1
3 8 4
a ab
a bc
c de
b bbb
bdebbb
The string is transformed as follows:
$$\texttt{a} \rightarrow \texttt{ab} \rightarrow \texttt{bcb} \rightarrow \texttt{bdeb} \rightarrow \texttt{bbbdebbb}$$