演劇の台本で、いくつかの言葉を別の言葉に置き換えたい。 置き換え規則は "a b" の形で、台本の中の a を b に変えるという意味だ。 規則は一つずつ順に使うのではなく、すべてまとめて一度に使う。 だから "Tom Ann" と "Ann Tom" の二つの規則があれば、二つの名前が入れ替わる。 台本の各行は、先頭の文字から左から右へ見ながら、次のように置き換える。 今の位置から始まる a を持つ規則のうち、a がいちばん長い規則を一つ選ぶ。 そのような規則があれば、その規則の b を書き、a の文字数だけ先へ進む。 なければ、今の文字をそのまま書き、一文字先へ進む。 書き込んだ b は二度と調べない。 a が単語の一部であっても置き換える。 大文字と小文字は別の文字で、a と b の中の記号（. * ( \ $ など）は特別な意味を持たず、その文字そのものだ。 一行目に規則の数 m、続く m 行に規則が一つずつ与えられる。 次の行に台本の行数 k、続く k 行に台本が一行ずつ与えられる。 置き換えた台本を入力の順に k 行で出力せよ。
入力
1 ≤ m ≤ 50。 a と b は空白を含まない ASCII 文字（コード 33～126）1～10 文字で、a と b の間に空白が一つある。 規則の a はすべて異なる（a と b は同じでもよい）。 1 ≤ k ≤ 20。 台本の各行は ASCII 文字（コード 32～126）1～1,000 文字で、空白で始まったり終わったりしない
出力
k 行
例 1 · stdin
3
Tom Ann
Ann Tom
To Mr.
2
Tom met Ann.
Ann told Tom: Today!
stdout
Ann met Tom.
Tom told Ann: Mr.day!
例 2 · stdin
2
a.b x
x a.b
1
a.b axb x xx
stdout
x aa.bb a.b a.ba.b
main.py
エラー一覧00F8 ↓ · ⇧F8 ↑
入力(stdin)
実行すると、これらの行が順に input()・標準入力に渡されます(実行中に入力を求めません)。
$ 準備完了
コードを入力して解くにはパソコンで開いてください。モバイルでは問題と解答を見られます。
ほかの言語では？言語別の解答を見る · 8 言語の解答
要は「一度の走査でまとめて」です。 各言語の置換関数（Python str.replace、JS・TS replaceAll、Java replace、C# Replace、Craykon 置き換え）は規則を一つしか扱わないので、規則ごとに順に呼ぶと Tom→Ann の後の Ann→Tom がいま変えた分まで戻してしまい、全部 Tom になります。 そこで位置ごとに「ここから始まるいちばん長い a」を辞書で探します。 a は 10 文字以下なので長さ 10 から 1 まで切り出して辞書にあるか聞けば十分です：Python dict、JS・TS Map.has、Java HashMap.containsKey、C# Dictionary.TryGetValue、C++ unordered_map::find、Craykon 辞書() と 含む、切り出しは 切り出す(i, len)。 C には辞書がないので 50 個の規則を strncmp(text + i, a, len) で一つずつ比べます。 Python なら re.escape した a を長い順に | でつないで re.sub すれば一度で済みます。 正規表現の | は左から試すので、短いほうが先だと To が Tom を横取りし、re.escape（JS では手で escape）を忘れると . が任意の文字に一致し、( は正規表現エラーになります。 Java の replaceAll も正規表現なので同じ問題があり、文字どおり置き換えるのは replace です。 ほかの落とし穴：先に書かれた規則を選ぶ（いちばん長いものでなければならない）、置き換えた後に一文字しか進まず a の残りをまた読む、結果をもう一度走査して b まで置き換える。
Pythonmain.py · 14 行
import reimport syslines = sys.stdin.read().split("\n")m = int(lines[0])rules = dict(line.split(" ") for line in lines[1:1 + m])k = int(lines[1 + m])# 긴 것부터 늘어놓은 a들을 | 로 잇는다. re.escape로 . * ( 같은 기호를 글자 그대로 찾게 한다.# 정규식의 | 는 왼쪽 것부터 맞춰 보므로, 긴 것이 앞에 있으면 그 자리에서 가장 긴 a가 걸린다.pattern = re.compile("|".join(re.escape(a) for a in sorted(rules, key=len, reverse=True)))for text in lines[2 + m:2 + m + k]: # re.sub는 왼쪽부터 한 번 훑고, 바꿔 넣은 글자는 다시 보지 않는다 print(pattern.sub(lambda mt: rules[mt.group()], text))
JavaScriptmain.js · 28 行
const lines = require("fs").readFileSync(0, "utf8").split("\n");const m = Number(lines[0]);const rules = new Map();for (const line of lines.slice(1, 1 + m)) { const [a, b] = line.split(" "); rules.set(a, b);}const k = Number(lines[1 + m]);function rewrite(text) { const out = []; let i = 0; while (i < text.length) { let len = Math.min(10, text.length - i); // 지금 자리에서 가장 긴 a부터 찾아본다 while (len > 0 && !rules.has(text.slice(i, i + len))) len--; if (len > 0) { out.push(rules.get(text.slice(i, i + len))); i += len; } else { out.push(text[i]); i++; } } return out.join("");}console.log(lines.slice(2 + m, 2 + m + k).map(rewrite).join("\n"));
TypeScriptmain.ts · 31 行
import { readFileSync } from "node:fs";const lines: string[] = readFileSync(0, "utf8").split("\n");const m = Number(lines[0]);const rules = new Map<string, string>();for (const line of lines.slice(1, 1 + m)) { const [a, b] = line.split(" "); rules.set(a, b);}const k = Number(lines[1 + m]);function rewrite(text: string): string { const out: string[] = []; let i = 0; while (i < text.length) { let len = Math.min(10, text.length - i); // 지금 자리에서 가장 긴 a부터 찾아본다 while (len > 0 && !rules.has(text.slice(i, i + len))) len--; const b = rules.get(text.slice(i, i + len)); if (len > 0 && b !== undefined) { out.push(b); i += len; } else { out.push(text[i]); i++; } } return out.join("");}console.log(lines.slice(2 + m, 2 + m + k).map(rewrite).join("\n"));
JavaMain.java · 37 行
import java.io.BufferedReader;import java.io.InputStreamReader;import java.io.IOException;import java.util.HashMap;import java.util.Map;public class Main { public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); int m = Integer.parseInt(in.readLine().trim()); Map<String, String> rules = new HashMap<>(); for (int r = 0; r < m; r++) { String[] p = in.readLine().split(" "); rules.put(p[0], p[1]); } int k = Integer.parseInt(in.readLine().trim()); StringBuilder out = new StringBuilder(); for (int t = 0; t < k; t++) { String text = in.readLine(); int i = 0; while (i < text.length()) { int len = Math.min(10, text.length() - i); // 지금 자리에서 가장 긴 a부터 찾아본다 while (len > 0 && !rules.containsKey(text.substring(i, i + len))) len--; if (len > 0) { out.append(rules.get(text.substring(i, i + len))); i += len; } else { out.append(text.charAt(i)); i++; } } out.append('\n'); } System.out.print(out); }}
C#Main.cs · 43 行
using System;using System.Collections.Generic;using System.Text;class Program{ static void Main() { int m = int.Parse(Console.ReadLine().Trim()); var rules = new Dictionary<string, string>(); for (int r = 0; r < m; r++) { string[] p = Console.ReadLine().Split(' '); rules[p[0]] = p[1]; } int k = int.Parse(Console.ReadLine().Trim()); var out_ = new StringBuilder(); for (int t = 0; t < k; t++) { string text = Console.ReadLine(); int i = 0; while (i < text.Length) { int len = Math.Min(10, text.Length - i); string b = null; // 지금 자리에서 가장 긴 a부터 찾아본다 while (len > 0 && !rules.TryGetValue(text.Substring(i, len), out b)) len--; if (len > 0) { out_.Append(b); i += len; } else { out_.Append(text[i]); i++; } } out_.Append('\n'); } Console.Write(out_); }}
C++main.cpp · 42 行
#include <algorithm>#include <iostream>#include <string>#include <unordered_map>int main() { std::ios::sync_with_stdio(false); int m, k; std::cin >> m; std::unordered_map<std::string, std::string> rules; for (int r = 0; r < m; r++) { std::string a, b; std::cin >> a >> b; rules[a] = b; } std::cin >> k; std::string text; std::getline(std::cin, text); // 수 뒤에 남은 줄 끝을 버린다 std::string out; for (int t = 0; t < k; t++) { std::getline(std::cin, text); size_t i = 0; while (i < text.size()) { size_t len = std::min<size_t>(10, text.size() - i); // 지금 자리에서 가장 긴 a부터 찾아본다 auto it = rules.end(); for (; len > 0; len--) { it = rules.find(text.substr(i, len)); if (it != rules.end()) break; } if (len > 0) { out += it->second; i += len; } else { out += text[i]; i++; } } out += '\n'; } std::cout << out;}
Cmain.c · 37 行
#include <stdio.h>#include <string.h>static char from[50][11], to[50][11];static int flen[50];static char text[1002];int main(void) { int m, k; scanf("%d", &m); for (int r = 0; r < m; r++) { scanf("%10s %10s", from[r], to[r]); flen[r] = (int)strlen(from[r]); } scanf("%d ", &k); /* 수 뒤의 줄바꿈까지 건너뛴다(대본은 빈칸으로 시작하지 않는다) */ for (int t = 0; t < k; t++) { if (!fgets(text, sizeof text, stdin)) break; text[strcspn(text, "\r\n")] = '\0'; int n = (int)strlen(text); for (int i = 0; i < n;) { int best = -1; /* 이 자리에서 시작하는 a 가운데 가장 긴 것 */ for (int r = 0; r < m; r++) if (flen[r] <= n - i && (best < 0 || flen[r] > flen[best]) && strncmp(text + i, from[r], flen[r]) == 0) best = r; if (best >= 0) { fputs(to[best], stdout); i += flen[best]; } else { putchar(text[i]); i++; } } putchar('\n'); } return 0;}
Craykonmain.cray · 34 行
m = コンソール.行読み().数に();rules = 辞書();繰り返す (r = 0; r < m; r++){ p = コンソール.行読み().分ける(" "); rules[p[0]] = p[1];}k = コンソール.行読み().数に();繰り返す (t = 0; t < k; t++){ text = コンソール.行読み(); out = []; i = 0; 間 (i < text.長さ) { len = 数学.小さい方(10, text.長さ - i); // 지금 자리에서 가장 긴 a부터 찾아본다 間 (len > 0 && !rules.含む(text.切り出す(i, len))) { len--; } もし (len > 0) { out.追加(rules[text.切り出す(i, len)]); i += len; } でなければ { out.追加(text[i]); i++; } } コンソール.書く(out.つなぐ(""));}