题目描述给定一个词典包含若干正确单词和若干待检查单词。对于每个待检查单词若它存在于词典中则输出is correct否则找出词典中所有可以通过一次编辑操作删除一个字母、替换一个字母、插入一个字母变为该单词的正确单词并按词典中的出现顺序输出。若没有则只输出单词加冒号。输入格式第一行为整数NNN表示数据集个数。每组数据第一部分为词典每行一个单词以#结束词典中单词互不相同最多100001000010000个长度≤15\le 15≤15。第二部分为待检查单词每行一个以#结束最多505050个。各组之间用空行分隔。输出格式对于每个待检查单词输出一行。若正确输出word is correct否则输出word:后跟所有可能的替换按词典顺序用空格分隔。若没有替换则冒号后直接换行。每组输出之间用空行分隔。样例输入1 i is has have be my more contest me too if award # me aware m contest hav oo or i fi mre #输出me is correct aware: award m: i my me contest is correct hav: has have oo: too or: i i is correct fi: i mre: more me题目分析本题的核心是判断两个单词是否可以通过一次编辑操作相互转换即编辑距离Levenshtein distance\texttt{Levenshtein distance}Levenshtein distance是否为111。由于单词长度不超过151515词典大小最多100001000010000待检查单词最多505050直接对每个待检查单词遍历词典计算编辑距离是可行的。但为了加速可以先按长度分组只检查长度相差不超过111的单词。编辑距离计算可采用动态规划但由于长度很小使用三层循环O(L1⋅L2)O(L_1 \cdot L_2)O(L1​⋅L2​)即可。或者利用编辑距离为111的特殊性质通过比较两个字符串的差异来快速判断。解题思路读入词典存入setstring便于精确查找同时保留vectorstring保持顺序。对于每个待检查单词若在词典中输出正确信息。否则遍历词典中的每个单词若长度差绝对值≥2\ge 2≥2跳过。计算编辑距离若为111则记录该单词。输出单词和冒号然后按顺序输出所有匹配的词典单词。编辑距离计算使用动态规划15×1515 \times 1515×15的表格常数极小。复杂度分析每个待检查单词遍历词典O(D⋅L2)O(D \cdot L^2)O(D⋅L2)其中D≤10000D \le 10000D≤10000L≤15L \le 15L≤15待检查单词最多505050总操作约50×10000×2251.125×10850 \times 10000 \times 225 1.125 \times 10^850×10000×2251.125×108在 C 中可接受实际运行1.3801.3801.380秒。空间复杂度O(D)O(D)O(D)。代码实现// Spell Checker// UVa ID: 671// Verdict: Accepted// Submission Date: 2017-06-01// UVa Run Time: 1.380s//// 版权所有C2017邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intmed(string S,string T){intcells[16][16];S S,T T;intMS.length()-1,NT.length()-1;cells[0][0]0;for(inti1;iM;i)cells[i][0]i;for(intj1;jN;j)cells[0][j]j;for(inti1;iM;i)for(intj1;jN;j){cells[i][j]min(cells[i-1][j],cells[i][j-1])1;if(S[i]T[j])cells[i][j]min(cells[i][j],cells[i-1][j-1]);elsecells[i][j]min(cells[i][j],cells[i-1][j-1]1);}returncells[M][N];}intmain(){cin.tie(0),cout.tie(0),ios::sync_with_stdio(false);intcases0;cincases;for(intc1;ccases;c){if(c1)cout\n;setstringwords;vectorstringdictionary;string word;while(cinword,word.front()!#)words.insert(word),dictionary.push_back(word);while(cinword,word.front()!#){coutword;if(words.find(word)!words.end()){cout is correct\n;continue;}cout:;intl1word.size();for(autoentry:dictionary){intl2entry.size();if(abs(l1-l2)2)continue;if(med(word,entry)1)cout entry;}cout\n;}}return0;}总结本题通过编辑距离计算判断单词间是否可以通过一次编辑操作转换并利用长度剪枝加速。关键点包括正确实现编辑距离动态规划。利用set快速判断单词是否在词典中。输出时按词典顺序列出所有可能的替换。注意每组输出之间的空行。该解法是编辑距离应用的典型例题适合作为字符串处理练习。