将数字串按字典序排序后只需检查相邻两串是否为前缀关系，即可判定集合是否可立即解码。
OJ: roj
题目 ID: 1474
难度:入门
标签:字符串排序字典树
创建: 2026-09-30 12:56
更新: 2026-10-06 00:24
题目描述
原题来自：ACM Pacific NW Region 1998。给出多组数据，每组 2~8 个只含 0/1 的数字串（1≤l≤10），以单独一行的数字 9 结束本组；判断每组中是否有一个数字串是另一个串的前缀，是则输出 Set t is not immediately decodable，否则输出 Set t is immediately decodable，t 为组号（从 1 开始）。输入样例：01 10 0010 0000 9、01 10 010 0000 9（两组，各以 9 结束），输出样例：Set 1 is immediately decodable、Set 2 is not immediately decodable。
思路
把每组数字串按字典序排序后，若存在某串是另一串的前缀，则必有一对相邻串满足前缀关系，因此只需检查排序后相邻两串是否为前缀即可。n≤8、l≤10，逐对比较总代价极小。
参考代码
Python 版：
python
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-04-18 10:00
# update_at: 2026-04-18 10:00
import sys
def has_prefix_relation(words: list[str]) -> bool:
"""判断给定单词集合中是否存在某一个串是另一个串的前缀。"""
sorted_words = sorted(words)
return any(
curr.startswith(prev)
for prev, curr in zip(sorted_words, sorted_words[1:])
)
def solve() -> None:
tokens = sys.stdin.read().split()
if not tokens:
return
case_idx = 1
current_words: list[str] = []
for token in tokens:
if token == '9':
is_decodable = not has_prefix_relation(current_words)
verdict = "immediately decodable" if is_decodable else "not immediately decodable"
print(f"Set {case_idx} is {verdict}")
case_idx += 1
current_words.clear()
else:
current_words.append(token)
if __name__ == "__main__":
solve()C++ 版（同一算法）：
cpp
/**
* Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
* rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
* rainboy的学习导航网站: https://idx.roj.ac.cn
* create_at: 2026-10-06 00:24
* update_at: 2026-10-06 00:24
*/
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
typedef long long ll;
const int MAXN = 15;
// str[i] : 第 i 个数字串，下标从 1 开始
string str[MAXN];
// 判断 a 是否是 b 的前缀
bool is_prefix(const string &a, const string &b) {
if (a.size() > b.size()) return false;
return b.compare(0, a.size(), a) == 0;
}
int main() {
string s;
int cas = 0;
while (cin >> s) {
if (s == "9") continue; // 单独的 9 是结束标志，不参与前缀判定
int n = 1;
str[1] = s;
while (cin >> s && s != "9") { // 读入本组的所有数字串，读到 9 结束
str[++n] = s;
}
sort(str + 1, str + 1 + n);
cas++;
// 字典序排序后，若某串是另一串的前缀，则必有一对相邻串满足前缀关系
bool decodable = true;
for (int i = 1; i < n; i++) {
if (is_prefix(str[i], str[i + 1])) decodable = false;
}
if (decodable)
cout << "Set " << cas << " is immediately decodable" << endl;
else
cout << "Set " << cas << " is not immediately decodable" << endl;
}
return 0;
}