概要

複数の文字列に対して「文字 \(a\) を文字 \(b\) に一括置換」を \(Q\) 回行った結果を、すべての文字列について効率よく求めます。

考察

各操作をそのまま全ファイル・全文字に適用すると、1回の置換で全体の文字数（最大 \(10^6\)）を走査することになり、これを \(Q\) 回（最大 \(10^5\)）繰り返すため \(O(Q \cdot \sum |S_i|)\) となって確実に間に合いません。

重要な気づきは、「最終的に各アルファベットがどの文字に変わるか」さえ分かれば、各文字列は最後に1回だけ変換すればよい、という点です。

ただし置換は逐次的に起こるため、例えば - 1回目: a -> b - 2回目: b -> c なら、最終的に a は c になります。
これは「a は1回目で b になり、その後 b がどうなるか（2回目以降）に従う」ためです。

この依存関係は 操作を逆から見る と簡単に処理できます。
後ろから考えると、「a -> b があったなら、最終結果としての a は、最終結果としての b と同じになる」という関係が成り立つからです。

アルゴリズム

1. 置換操作 \((a_j, b_j)\) をすべて読み取って配列に保持する。
2. mp[x] を「文字 x（0〜25）が最終的に何になるか」を表す配列として用意し、最初は mp[x] = x とする。
3. 操作を 逆順 に処理する。逆順で見たとき、操作 a -> b は
   • mp[a] = mp[b] と更新すればよい。
     これで「a は最終的に b が最終的になる文字へ行く」ことを表せます。
4. mp が完成したら、各文字列の各文字を mp に従って変換して出力する。
   • 実装では str.maketrans と translate を使い、1回の変換で高速に処理しています。

（例）操作が a->b, b->c のとき、逆順に見ると
- まず b->c：mp[b]=mp[c]=c - 次に a->b：mp[a]=mp[b]=c
となり、a が最終的に c へ行くことが正しく求まります。

計算量

• 時間計算量: \(O(Q + \sum_{i=1}^{N} |S_i| + 26)\)
  （写像作成が \(O(Q)\)、文字列変換が合計 \(O(\sum |S_i|)\)）
• 空間計算量: \(O(Q + \sum_{i=1}^{N} |S_i|)\)
  （入力保持と操作列、写像は \(O(26)\) で無視できる）

実装のポイント

• 逆順処理が核心です：mp[a] = mp[b] を後ろから行うことで、後続の置換の影響を自然に取り込めます。

• Pythonでは大量入力に備えて sys.stdin.buffer.read() でまとめて読み取ると安定します。

• 文字変換はループで1文字ずつ置き換えるより、translate を使うと簡潔かつ高速です。

  ソースコード

import sys

def main():
    data = sys.stdin.buffer.read().split()
    it = iter(data)
    N = int(next(it))
    Q = int(next(it))

    strings = [next(it).decode() for _ in range(N)]

    ops = []
    for _ in range(Q):
        a = next(it).decode()
        b = next(it).decode()
        ops.append((ord(a) - 97, ord(b) - 97))

    mp = list(range(26))
    for a, b in reversed(ops):
        mp[a] = mp[b]

    mapped = ''.join(chr(97 + mp[i]) for i in range(26))
    table = str.maketrans('abcdefghijklmnopqrstuvwxyz', mapped)

    out = [s.translate(table) for s in strings]
    sys.stdout.write('\n'.join(out))

if __name__ == "__main__":
    main()

この解説は gpt-5.2-high によって生成されました。