← 返回题目列表

AtCoder · awc0018_c

C. 批量字符转换

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

分数: 300 分

问题陈述

Takahashi 正在开发一个文本编辑器。该编辑器具有跨多个文本文件执行批量字符替换的功能。

有一天,高桥开业了 N 文本文件。每个文件包含一行,由一串小写英文字母组成。

高桥将表演 Q 按顺序对这些文件进行替换操作。在每次操作中,所有当前文件中包含的特定字符都会立即替换为另一个字符。

所有替换操作完成后,输出每个文件中写入的字符串。

约束

  • 1 \leq N \leq 10^5
  • 1 \leq Q \leq 10^5
  • 1 \leq |S_i| \leq 10^5
  • \sum_{i=1}^{N} |S_i| \leq 10^6
  • S_i 仅由小写英文字母组成
  • a_j, b_j 为小写英文字母

输入

N Q
S_1
S_2
:
S_N
a_1 b_1
a_2 b_2
:
a_Q b_Q
  • 第一行包含 N,文件数量,以及 Q,替换操作的数量,以空格分隔。
  • 从第 2 行到 (N + 1)第行,给出了每个文件中写入的字符串。
  • 的 (1 + i)- 第行包含字符串 S_i 写在 i-第一个文件。
  • S_i 仅由小写英文字母组成。
  • 从 (N + 2)第 行 (N + Q + 1)第行,给出了每个替换操作的详细信息。
  • 的 (N + 1 + j)- 第行包含原始字符 a_j 要替换的字符和目标字符 b_j 在 j第一个操作,以空格分隔。
  • a_j 和 b_j 都是一个小写英文字母。

输出

T_1
T_2
:
T_N
  • 输出 N 行,每行包含所有替换操作完成后对应文件中的字符串。
  • 的 i- 第行应包含字符串 T_i 写在 i-第一个文件。

样本输入 1

3 2
abc
dog
banana
a b
b c

示例输出 1

ccc
dog
ccncnc

示例输入 2

2 3
hello
world
l x
o a
x l

示例输出 2

hella
warld

示例输入 3

5 5
abcdefghij
programming
contest
algorithm
datastructure
a z
e a
z e
t s
s t

示例输出 3

ebcdafghij
progremming
contatt
elgorithm
detettructura

示例输入 4

10 8
thequickbrownfoxjumpsoverthelazydog
abcdefghijklmnopqrstuvwxyz
aabbccddee
zzzzzyyyyyxxxxx
helloworldfromcompetitiveprogramming
substitutioncipherexample
replacementoperation
queriesandfiles
multiplestrings
finaloutputtest
a b
b c
c d
d e
e f
f g
g h
z a

示例输出 4

thhquihkhrownhoxjumpsovhrthhlhayhoh
hhhhhhhhijklmnopqrstuvwxya
hhhhhhhhhh
aaaaayyyyyxxxxx
hhlloworlhhromhomphtitivhprohrhmminh
suhstitutionhiphhrhxhmplh
rhplhhhmhntophrhtion
quhrihshnhhilhs
multiplhstrinhs
hinhloutputthst

示例输入 5

1 1
a
a b

示例输出 5

b