题目描述一组符号的编码称为即时可解码immediately decodable \texttt{immediately decodable}immediately decodable如果不存在一个码字是另一个码字的前缀。例如码集合{01, 10, 0010, 0000}是即时可解码的而{01, 10, 010, 0000}不是因为01是010的前缀。本题给定若干组二进制码每组以单独一行9结束要求判断每组是否即时可解码。输入格式输入包含多组记录每组由若干个二进制码长度1 11到10 1010位组成每组至少2 22个码最多8 88个码。每组以一行包含单个字符9的记录作为分隔符。分隔符不属于该组。输入可能包含多组直到文件结束。输出格式对于每组输出一行格式为Set X is immediately decodable.或Set X is not immediately decodable.其中X XX为组编号从1 11开始。样例输入01 10 0010 0000 9 01 10 010 0000 9输出Set 1 is immediately decodable. Set 2 is not immediately decodable.题目分析本题要求检查一个字符串集合中是否存在一个字符串是另一个字符串的前缀。由于每组码的数量最多8 88长度最多10 1010可以直接两两比较检查是否一个以另一个开头。复杂度极低。解题思路逐行读入输入。对于每一组读取所有码字直到遇到行9为止。在读取过程中维护一个已读码字的列表。对于每个新码字检查它是否与已读的某个码字存在前缀关系即新码字以已读码字开头或已读码字以新码字开头。若存在则标记该组不可解码。继续读取本组剩余码字虽然已判定不可解码但仍需读完本组以便处理后续组。输出时根据标记输出相应信息。注意输入可能以空行结束但题目未明确说明代码中若遇到空行则退出实际在线评测中不会有空行但为健壮性可处理。复杂度分析每组最多8 88个码字每个长度最多10 1010两两比较时间复杂度为O ( 8 2 × 10 ) O ( 1 ) O(8^2 \times 10) O(1)O(82×10)O(1)。空间复杂度O ( 1 ) O(1)O(1)。代码实现// Immediate Decodability// UVa ID: 644// Verdict: Accepted// Submission Date: 2016-08-23// UVa Run Time: 0.020s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intmain(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);intcases0;string line;while(true){vectorstringdecoded;booldecodabletrue;while(getline(cin,line),line.length()0line.front()!9){if(!decodable)continue;for(inti0;idecoded.size();i)if(line.find(decoded[i])0||decoded[i].find(line)0){decodablefalse;break;}decoded.push_back(line);}if(line.length()0)break;coutSet cases;if(decodable)cout is immediately decodable\n;elsecout is not immediately decodable\n;}return0;}总结本题通过逐一比较新码字与已读码字检查前缀关系判断每组是否即时可解码。由于数据规模极小直接暴力比较即可。注意读入时需读完整个组即使已判定不可解码也要继续读取本组剩余行以免影响后续组的解析。该解法简单高效体现了前缀码判定的基本方法。
UVa 644 Immediate Decodability
题目描述一组符号的编码称为即时可解码immediately decodable \texttt{immediately decodable}immediately decodable如果不存在一个码字是另一个码字的前缀。例如码集合{01, 10, 0010, 0000}是即时可解码的而{01, 10, 010, 0000}不是因为01是010的前缀。本题给定若干组二进制码每组以单独一行9结束要求判断每组是否即时可解码。输入格式输入包含多组记录每组由若干个二进制码长度1 11到10 1010位组成每组至少2 22个码最多8 88个码。每组以一行包含单个字符9的记录作为分隔符。分隔符不属于该组。输入可能包含多组直到文件结束。输出格式对于每组输出一行格式为Set X is immediately decodable.或Set X is not immediately decodable.其中X XX为组编号从1 11开始。样例输入01 10 0010 0000 9 01 10 010 0000 9输出Set 1 is immediately decodable. Set 2 is not immediately decodable.题目分析本题要求检查一个字符串集合中是否存在一个字符串是另一个字符串的前缀。由于每组码的数量最多8 88长度最多10 1010可以直接两两比较检查是否一个以另一个开头。复杂度极低。解题思路逐行读入输入。对于每一组读取所有码字直到遇到行9为止。在读取过程中维护一个已读码字的列表。对于每个新码字检查它是否与已读的某个码字存在前缀关系即新码字以已读码字开头或已读码字以新码字开头。若存在则标记该组不可解码。继续读取本组剩余码字虽然已判定不可解码但仍需读完本组以便处理后续组。输出时根据标记输出相应信息。注意输入可能以空行结束但题目未明确说明代码中若遇到空行则退出实际在线评测中不会有空行但为健壮性可处理。复杂度分析每组最多8 88个码字每个长度最多10 1010两两比较时间复杂度为O ( 8 2 × 10 ) O ( 1 ) O(8^2 \times 10) O(1)O(82×10)O(1)。空间复杂度O ( 1 ) O(1)O(1)。代码实现// Immediate Decodability// UVa ID: 644// Verdict: Accepted// Submission Date: 2016-08-23// UVa Run Time: 0.020s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intmain(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);intcases0;string line;while(true){vectorstringdecoded;booldecodabletrue;while(getline(cin,line),line.length()0line.front()!9){if(!decodable)continue;for(inti0;idecoded.size();i)if(line.find(decoded[i])0||decoded[i].find(line)0){decodablefalse;break;}decoded.push_back(line);}if(line.length()0)break;coutSet cases;if(decodable)cout is immediately decodable\n;elsecout is not immediately decodable\n;}return0;}总结本题通过逐一比较新码字与已读码字检查前缀关系判断每组是否即时可解码。由于数据规模极小直接暴力比较即可。注意读入时需读完整个组即使已判定不可解码也要继续读取本组剩余行以免影响后续组的解析。该解法简单高效体现了前缀码判定的基本方法。
