UVa 508 Morse Mismatches
题目描述
题目要求根据给定的摩尔斯电码表和一个单词词典，对每个输入的摩尔斯电码串进行匹配。匹配规则如下：
- 若只有一个单词的摩尔斯电码与输入完全相同，则输出该单词。
- 若有多个单词的摩尔斯电码完全相同，则输出其中长度最短的单词（若仍有多个，任选一个），并在其后加
!。 - 若无完全匹配，则找出匹配最长公共前缀的单词（即前缀长度等于输入长度或单词长度中的较小值），并选择长度差异最小的单词（即∣len_morse−len_word∣|len\_morse - len\_word|∣len_morse−len_word∣最小），输出该单词并在其后加
?。
输入格式
输入包含三部分：
- 摩尔斯电码表：每行一个大写字母或数字，后跟一个空格或多个空格，再跟其摩尔斯电码（
.和-，长度不超过666）。以单独一行*结束。 - 词典：每行一个单词（大写字母和数字，长度不超过101010），最多100100100个。以单独一行
*结束。 - 摩尔斯电码串：每行一个摩尔斯电码串（由
.和-组成，长度不超过808080），以单独一行*结束。
输出格式
对于每个摩尔斯电码串，输出一行对应的匹配单词（可能带!或?后缀）。
样例
输入
A .- B -... C -.-. D -.. E . F ..-. G --. H .... I .. J .--- K -.- L .-.. M -- N -. O --- P .--. Q --.- R .-. S ... T - U ..- V ...- W .-- X -..- Y -.-- Z --.. 0 ----- 1 .---- 2 ..--- 3 ...-- 4 ....- 5 ..... 6 -.... 7 --... 8 ---.. 9 ----. * A B C D E F G H I J K L M N O P Q R S T U V W X Y Z 0 1 2 3 4 5 6 7 8 9 * . . . - . . . - . . . - . . . - . . . - . . . - . . . - . . . - . . . - . . . - . . . - *输出
SOS题目分析
本题的核心是字符串匹配，需要处理完全匹配和最长公共前缀匹配两种情况。
预处理
- 读取摩尔斯电码表，建立字符到摩尔斯电码的映射。
- 读取词典，将每个单词转换为摩尔斯电码串，存储单词和对应的摩尔斯电码。
匹配逻辑
对于每个输入的摩尔斯电码串mmm：
- 遍历所有词典单词，计算mmm与单词摩尔斯电码的匹配长度（逐字符比较直到不匹配或任一结束）。
- 若匹配长度等于两者长度，则完全匹配，加入候选列表。
- 若不完全匹配，则计算长度差异，记录差异最小的单词。
完全匹配优先：
- 若完全匹配候选数为111，输出该单词。
- 若完全匹配候选数>1>1>1，选择其中最短的单词（若长度相同任选），输出并加
!。 - 若无完全匹配，输出长度差异最小的单词并加
?。
复杂度分析
词典大小≤100\le 100≤100，每个摩尔斯电码串长度≤80\le 80≤80，每次匹配O(80)O(80)O(80)，总复杂度可接受。
代码实现
// Morse Mismatches// UVa ID: 508// Verdict: Accepted// Submission Date: 2017-04-25// UVa Run Time: 0.000s//// 版权所有（C）2017，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;intmain(intargc,char*argv[]){cin.tie(0),cout.tie(0),ios::sync_with_stdio(false);map<char,string>table;vector<string>word,context;charletter;string field;while(cin>>letter,letter!='*'){cin>>field;table[letter]=field;}while(cin>>field,field!="*"){string code;for(autoc:field)code+=table[c];word.push_back(field);context.push_back(code);}while(cin>>field,field!="*"){vector<string>perfectly;string flawed=word.front();intminDiff=102400;for(inti=0;i<word.size();i++){size_t matched=0;for(size_t j=0;j<field.size()&&j<context[i].size();j++){if(field[j]!=context[i][j])break;matched++;}if(matched==field.size()&&matched==context[i].size())perfectly.push_back(word[i]);else{if(matched==min(context[i].size(),field.size())){intdiff=abs((int)context[i].size()-(int)field.size());if(diff<minDiff){minDiff=diff;flawed=word[i];}}}}if(perfectly.size()==1)cout<<perfectly.front()<<'\n';else{if(perfectly.size()>1)cout<<perfectly.front()<<"!\n";elsecout<<flawed<<"?\n";}}return0;}