想把剧本里的一些词换成别的词。 替换规则的形式是 "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。 剧本每行是 1～1,000 个 ASCII 字符（编码 32～126），不以空格开头或结尾
输出
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 没有字典，用 strncmp(text + i, a, len) 逐个比较 50 条规则。 Python 用 re.escape 后的 a 按从长到短以 | 连接再 re.sub，一次就能完成。 正则的 | 从左往右尝试，短的在前面时 To 会抢走 Tom；忘了 re.escape（JS 要手动转义）时 . 会匹配任意字符，( 会导致正则错误。 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.连接(""));}