题目描述Soundex\texttt{Soundex}Soundex编码系统用于将发音相似或拼写相似的名称编码以便检索。给定若干由大写字母组成的名字长度111到202020要求为每个名字生成其Soundex\texttt{Soundex}Soundex编码。编码规则如下规则1\texttt{1}1. 编码始终以一个字母名字的首字母开头后跟三个数字。规则2\texttt{2}2. 字母A、E、I、O、U、Y、W、H不编码但会中断连续的编码序列即它们不产生数字但会使前后编码数字不会因相同而被合并。规则3\texttt{3}3. 其他字母按映射表转换为数字但若该字母与前面一个编码字母包括首字母映射到相同数字则忽略该字母不重复编码。规则4\texttt{4}4. 映射表B, P, F, V→111C, S, K, G, J, Q, X, Z→222D, T→333L→444M, N→555R→666。规则5\texttt{5}5. 编码不足333位数字时用0补齐超过333位时截断。规则6\texttt{6}6. 最终Soundex\texttt{Soundex}Soundex码由首字母加333位数字构成。输入格式输入包含若干行每行一个名字仅由大写字母组成长度不超过202020。输入以文件结束终止。输出格式第一行输出表头NAME从第101010列开始SOUNDEX CODE从第353535列开始列号从111计数。随后每行输出名字和其 Soundex 编码名字从第101010列开始编码从第353535列开始均左对齐。最后一行输出END OF OUTPUT从第202020列开始。样例输入LEE KUHNE EBEL EBELSON SCHAEFER SCHAAK样例输出NAME SOUNDEX CODE LEE L000 KUHNE K500 EBEL E140 EBELSON E142 SCHAEFER S160 SCHAAK S200 END OF OUTPUT题目分析Soundex\texttt{Soundex}Soundex编码生成过程可分解为以下步骤步骤1\texttt{1}1. 将名字中每个字母转换为对应的数字编码字母表中262626个字母的映射得到数字串DDD其中非编码字母对应数字000。步骤2\texttt{2}2. 去除DDD中相邻重复的数字但需注意规则2\texttt{2}2中非编码字母会“中断”连续编码序列。即若当前数字为000则它不保留但会将“上一个有效数字”重置使得后续数字即使与之前相同也被保留。等价于从第二个字母开始遍历若当前字母对应的数字为000则更新“上一个有效数字”为000否则若当前数字不等于上一个有效数字则保留当前数字并更新上一个有效数字为当前数字否则跳过。步骤3\texttt{3}3. 编码以首字母开头随后跟上步骤2\texttt{2}2中保留的所有非零数字按顺序。最后补齐或截断至333个数字。该过程没有歧义可直接模拟。解题思路实现算法如下步骤1\texttt{1}1. 预定义数组digits[26]\textit{digits}[26]digits[26]存储 A-Z 对应的数字非编码字母为000。步骤2\texttt{2}2. 对于每个名字namenamename初始化结果字符串codecodecode为其首字母。初始化变量last\textit{last}last为digits[name.front() -A]表示上一个有效编码数字。步骤3\texttt{3}3. 从第二个字符下标111开始遍历对每个字符ccc计算dd ddigits[c - A]。若d0d 0d0则设置last0\textit{last} 0last0中断连续序列不添加任何数字。否则若d≠lastd \ne \textit{last}dlast则将字符d′0′d 0d′0′添加到codecodecode尾部并更新lastd\textit{last} dlastd若dlastd \textit{last}dlast则跳过。步骤4\texttt{4}4. 在codecodecode尾部补充0直到长度达到444若长度超过444则截取前444个字符。步骤5\texttt{5}5. 输出时名字从第101010列开始左对齐宽度252525编码从第353535列开始。代码实现// Soundex Indexing// UVa ID: 739// Verdict: Accepted// Submission Date: 2016-11-30// UVa Run Time: 0.000s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intmain(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);intdigits[26]{0,1,2,3,0,1,2,0,0,2,2,4,5,5,0,1,2,6,2,3,0,1,0,2,0,2};coutstring(9, )setw(25)leftNAMESOUNDEX CODE\n;string name;while(cinname){string code;codename.front();intlastdigits[name.front()-A];for(inti1;iname.length();i){intddigits[name[i]-A];if(d0)last0;elseif(d!last){codechar(0d);lastd;}}while(code.length()4)code.push_back(0);if(code.length()4)codecode.substr(0,4);coutstring(9, )setw(25)leftnamecode\n;}coutstring(19, )END OF OUTPUT\n;return0;}总结本题通过直接模拟Soundex\texttt{Soundex}Soundex编码规则实现关键在于正确处理非编码字母对连续序列的打断效果。采用“上一个有效数字”变量记录最近保留的非零数字当遇到零时重置该变量即可实现规则2\texttt{2}2和3\texttt{3}3。输出格式要求严格的列对齐利用setw和左对齐控制。算法时间复杂度O(L)O(L)O(L)空间复杂度O(1)O(1)O(1)适用于长度不超过202020的名字。该解法简洁清晰准确实现了所有规则。