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输出该单词。若完全匹配候选数111选择其中最短的单词若长度相同任选输出并加!。若无完全匹配输出长度差异最小的单词并加?。复杂度分析词典大小≤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//// 版权所有C2017邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intmain(intargc,char*argv[]){cin.tie(0),cout.tie(0),ios::sync_with_stdio(false);mapchar,stringtable;vectorstringword,context;charletter;string field;while(cinletter,letter!*){cinfield;table[letter]field;}while(cinfield,field!*){string code;for(autoc:field)codetable[c];word.push_back(field);context.push_back(code);}while(cinfield,field!*){vectorstringperfectly;string flawedword.front();intminDiff102400;for(inti0;iword.size();i){size_t matched0;for(size_t j0;jfield.size()jcontext[i].size();j){if(field[j]!context[i][j])break;matched;}if(matchedfield.size()matchedcontext[i].size())perfectly.push_back(word[i]);else{if(matchedmin(context[i].size(),field.size())){intdiffabs((int)context[i].size()-(int)field.size());if(diffminDiff){minDiffdiff;flawedword[i];}}}}if(perfectly.size()1)coutperfectly.front()\n;else{if(perfectly.size()1)coutperfectly.front()!\n;elsecoutflawed?\n;}}return0;}