← 返回题目列表

AtCoder · icpc2014spring_h

H. RLE 更换

中文机器翻译题面 查看原题

问题陈述

在JAG王国中,ICPC(有意压缩编程代码)是常见的编程语言之一。 该语言的程序仅包含大写英文字母 相同的字母经常在 ICPC 程序中重复出现。 因此,JAG王国的程序员更喜欢将ICPC程序压缩为 游程长度编码 以便管理超大规模的 ICPC 程序。

游程长度编码(RLE)是一种字符串压缩方法,相同字母的每个最大序列都由一对字母和长度进行编码。 例如,字符串“RRRRLEEE”在 RLE 中表示为“R4L1E3”。

现在,您管理许多由 RLE 编码的 ICPC 程序。 您正在为 RLE 编码的 ICPC 程序开发一个编辑器,现在您想要实现替换功能。 给定由 RLE 编码的三个字符串 $A$、$B$ 和 $C$,您的任务是实现一个函数,将 $A$ 中第一次出现的子字符串 $B$ 替换为 $C$,并输出由 RLE 编码的编辑后的字符串。 如果 $B$ 没有出现在 $A$ 中,则必须输出由 RLE 编码且不做任何更改的 $A$。


输入

输入由三行组成。

$A$
$B$
$C$

这些行分别表示由 RLE 编码的字符串 $A$、$B$ 和 $C$。 每行都具有以下格式:

$c_1$ $l_1$ $c_2$ $l_2$ $\ldots$ $c_n$ $l_n$ \$

每个 $c_i$ ($1 \leq i \leq n$) 是一个大写英文字母 (A-Z) 和 $l_i$ ($1 \leq i \leq n$, $1 \leq l_i \leq 10^8$) 是一个整数,表示 $c_i$ 的重复长度。 字母和整数对的数量 $n$ 满足 $1 \leq n \leq 10^3$。 终端符号 $ 表示RLE编码的字符串的结尾。 字母和整数由一个空格分隔。 保证 $c_i \neq c_{i+1}$ 对于任何 $1 \leq i \leq n-1$ 成立。

输出

如果$B$出现在$A$中,则将$A$中第一次出现的子字符串$B$替换为$C$,并输出RLE编码的字符串。 输出必须具有以下格式:

$c_1$ $l_1$ $c_2$ $l_2$ $\ldots$ $c_m$ $l_m$ \$

这里,$1 \leq i \leq m-1$ 的 $c_i \neq c_{i+1}$ 和 $1 \leq i \leq m$ 的 $l_i \gt 0$ 必须成立。


示例输入 1

R 100 L 20 E 10 $
R 5 L 10 $
X 20 $

样本输入 1 的输出

R 95 X 20 L 10 E 10 $

示例输入 2

A 3 B 3 A 3 $
A 1 B 3 A 1 $
A 2 $

样本输入 2 的输出

A 6 $