We want to change some words in a play script.
A rule has the form "a b" and means: change a in the script to b.
The rules are not applied one after another; they are all applied at once.
So with the two rules "Tom Ann" and "Ann Tom", the two names swap.
For each script line, scan from the first character left to right, as follows.
Among the rules whose a starts at the current position, pick the one with the longest a.
If there is such a rule, write its b and move forward by the length of a.
If there is none, write the current character as it is and move forward by one character.
A b that was written is never examined again.
A match is replaced even when a is only part of a word.
Uppercase and lowercase letters are different, and symbols inside a and b (. * ( \ $ and so on) have no special meaning; each is just that character.
The first line gives the number of rules m, and the next m lines give one rule each.
The next line gives the number of script lines k, and the next k lines give the script.
Print the rewritten script in input order, k lines.
Input
1 ≤ m ≤ 50. a and b are 1–10 ASCII characters without spaces (codes 33–126), with one space between a and b. All a are different (a and b may be equal). 1 ≤ k ≤ 20. Each script line has 1–1,000 ASCII characters (codes 32–126) and does not start or end with a space
Output
k lines
Example 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!
Example 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
Error List00F8 ↓ · ⇧F8 ↑
Input (stdin)
When you run, these lines are fed to input()/stdin in order (the program doesn't stop to ask).
$ Ready
Open this on a computer to write and run code. On mobile you can read the problem and the solutions.
In other languagesShow solutions by language · 8 languages
The point is 'one scan, all at once'. Each language's replace function (Python str.replace, JS/TS replaceAll, Java replace, C# Replace, Craykon Replace) handles one rule, so calling it rule by rule makes Ann→Tom undo what Tom→Ann just did, and everything becomes Tom. Instead, at each position look up 'the longest a starting here' in a dictionary. Since a is at most 10 characters, cut lengths 10 down to 1 and ask whether the dictionary has it: Python dict, JS/TS Map.has, Java HashMap.containsKey, C# Dictionary.TryGetValue, C++ unordered_map::find, Craykon Dict() with Contains and Substring(i, len). C has no dictionary, so compare the 50 rules one by one with strncmp(text + i, a, len). In Python, re.sub with the re.escaped a's joined by |, longest first, does it in one call. Regex | tries alternatives left to right, so with a short one first, To steals Tom; without re.escape (in JS, escape by hand) . matches any character and ( is a regex error. Java replaceAll is also a regex with the same issue; the literal one is replace. Other traps: picking the rule listed first (it must be the longest), moving only one character after a replacement so the rest of a is read again, and scanning the result again so b gets replaced too.
Pythonmain.py · 14 lines
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 lines
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 lines
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 lines
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 lines
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 lines
#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 lines
#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 lines
m = Console.ReadLine().ToNumber();rules = Dict();for (r = 0; r < m; r++){ p = Console.ReadLine().Split(" "); rules[p[0]] = p[1];}k = Console.ReadLine().ToNumber();for (t = 0; t < k; t++){ text = Console.ReadLine(); out = []; i = 0; while (i < text.Length) { len = Mathf.Min(10, text.Length - i); // 지금 자리에서 가장 긴 a부터 찾아본다 while (len > 0 && !rules.Contains(text.Substring(i, len))) { len--; } if (len > 0) { out.Add(rules[text.Substring(i, len)]); i += len; } else { out.Add(text[i]); i++; } } Console.WriteLine(out.Join(""));}