[ABSEC0001] 图书检索 题解
题目概述
给定一个书册名录（ 个字符串）和一个待查书名 ，需要按以下优先级检索：
- 精确匹配：若 在名录中，输出
"Exact Match" - 模糊匹配：找出所有与 长度相同且汉明距离恰好为 1 的书名，按输入顺序输出，空格分隔
- 无结果：若以上都不满足，输出
"No Result"
知识点考察
- 字符串处理
- 汉明距离（Hamming Distance）
- 条件分支与遍历
- 格式控制输出
解题思路
第一步：预处理与精确匹配
将名录存储在数组/vector 中，先检查 是否存在于名录中。如果存在，直接输出 "Exact Match" 并结束程序。
第二步：模糊匹配（汉明距离为 1）
遍历名录中的每个字符串 ，筛选满足以下条件的书名：
- 与 的汉明距离恰好为 1，即：
- 长度相同
- 恰好有 1 个位置字符不同
- 其余位置完全相同
将匹配到的字符串按遍历顺序（即输入顺序）收集起来。
第三步：输出结果
- 如果匹配列表非空，用空格连接后输出
- 如果匹配列表为空，输出
"No Result"
⚠️ 注意：即使精确匹配存在，也要同时进行精确匹配优先判断。题目要求先检查精确存在，不能先收集模糊匹配再输出。
汉明距离计算
对于两个长度相同的字符串 和 ，汉明距离为：
distance = count of positions i where a[i] != b[i]
本题只关心汉明距离是否恰好为 1。
优化技巧（可选）
由于长度 ，即使暴力比较每个字符，单次比较复杂度 ，总复杂度 ，完全可行。
代码实现
C++
#include <bits/stdc++.h>
using namespace std;
// 计算两个等长字符串的汉明距离
int hammingDistance(const string& a, const string& b) {
int cnt = 0;
for (int i = 0; i < (int)a.size(); i++) {
if (a[i] != b[i]) cnt++;
}
return cnt;
}
int main() {
int N;
cin >> N;
vector<string> books(N);
for (int i = 0; i < N; i++) {
cin >> books[i];
}
string target;
cin >> target;
// 1. 精确匹配
for (const string& s : books) {
if (s == target) {
cout << "Exact Match\n";
return 0;
}
}
// 2. 模糊匹配：汉明距离为 1
vector<string> matches;
for (const string& s : books) {
if (s.length() == target.length() && hammingDistance(s, target) == 1) {
matches.push_back(s);
}
}
// 3. 输出结果
if (matches.empty()) {
cout << "No Result\n";
} else {
for (int i = 0; i < (int)matches.size(); i++) {
if (i > 0) cout << ' ';
cout << matches[i];
}
cout << '\n';
}
return 0;
}
Python
def hamming_distance(a, b):
return sum(1 for x, y in zip(a, b) if x != y)
N = int(input())
books = [input().strip() for _ in range(N)]
target = input().strip()
# 1. 精确匹配
if target in books:
print("Exact Match")
exit()
# 2. 模糊匹配
matches = []
for s in books:
if len(s) == len(target) and hamming_distance(s, target) == 1:
matches.append(s)
# 3. 输出结果
if not matches:
print("No Result")
else:
print(' '.join(matches))
Java
import java.util.*;
public class Main {
public static int hammingDistance(String a, String b) {
int cnt = 0;
for (int i = 0; i < a.length(); i++) {
if (a.charAt(i) != b.charAt(i)) cnt++;
}
return cnt;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
String[] books = new String[N];
for (int i = 0; i < N; i++) {
books[i] = sc.next();
}
String target = sc.next();
// 1. 精确匹配
for (String s : books) {
if (s.equals(target)) {
System.out.println("Exact Match");
return;
}
}
// 2. 模糊匹配
List<String> matches = new ArrayList<>();
for (String s : books) {
if (s.length() == target.length() && hammingDistance(s, target) == 1) {
matches.add(s);
}
}
// 3. 输出结果
if (matches.isEmpty()) {
System.out.println("No Result");
} else {
System.out.println(String.join(" ", matches));
}
sc.close();
}
}
复杂度分析
- 时间复杂度：，其中 为名录大小， 为字符串长度（），遍历所有书名并计算汉明距离。
- 空间复杂度：，存储名录和匹配结果。
易错点提醒
| 易错点 | 说明 |
|---|---|
| ❌ 精确匹配与模糊匹配的优先级 | 必须先检查精确匹配，即使存在汉明距离为 1 的书名，也应优先输出 "Exact Match" |
| ❌ 长度不同的字符串 | 不能计算汉明距离，必须先检查长度相等，否则会越界或逻辑错误 |
| ❌ 输出格式 | 多个结果之间用空格隔开，末尾不能有多余空格，通常使用循环判断或 join 处理 |
| ❌ 区分"恰好 1 个"和"至少 1 个" | 必须恰好为 1，不能是 0（精确匹配已在第一步处理）或大于 1 |
测试用例
| 输入 | 输出 | 说明 |
|---|---|---|
3abcdefghiabc |
Exact Match |
精确存在 |
3abcadcaecabc |
精确匹配优先于模糊匹配 | |
3abcadcxyzaec |
abc adc |
两个模糊匹配结果 |
2abcxyzdef |
No Result |
既无精确也无模糊匹配 |
1abcabcd |
长度不同，不计入模糊匹配 |
扩展思考
1. 如果数据规模更大（）怎么办？
可以考虑用 Trie 树（字典树）来加速查询，对于每个位置构造通配符索引（如将 abc 拆分为 *bc, a*c, ab*），但本题 ，暴力完全足够。
2. 如果要求汉明距离为 （ 为任意值）？
只需将 hammingDistance == 1 改为 hammingDistance == k 即可，核心逻辑不变。
总结
本题是字符串处理的入门题，核心在于：
- 理解汉明距离的定义
- 严格按照优先级进行判断
- 注意输出格式的控制
希望这篇题解对您有帮助！如有任何疑问，欢迎在评论区留言讨论。
暂无评论