UVa 373 Romulan Spelling

题目描述罗慕兰人使用一种可以用英文字母和标点符号近似的语言。然而他们的拼写规则比英语更奇怪。特别地他们有一条规则G在P之前除非在E之后或者当发音为X时如npgukbor或wpguk中的情况。操作上可以通过字符串PGUK在单词中出现来检测 X 发音。此外罗慕兰人的大写规则与我们的不同因此大写字母可以出现在单词的任何位置。要求给定包含罗慕兰文本的行根据上述规则进行拼写校正。输入格式输入包含多行罗慕兰文本每行不超过707070个字符包括空格。输出格式输出校正后的文本。样例输入I rpEpgvpd tKp wgprd tgpEp of tgp from my npgukBor sam wKo gn turn rpEgpvpd tKp wgprd tgpEp of tpg from Kgs ngpukBor Karry,样例输出I rpEpgvpd tKp wgprd tgpEp of tgp from my npgukBor sam wKo gn turn rpEgpvpd tKp wgprd tgpEp of tgp from Kgs ngpukBor Karry,题目分析问题的本质这是一个字符串局部交换问题。需要根据规则检测并交换相邻的G和P。规则总结规则说“G before P except after E or when pronounced X as in npgukbor or wpguk.”翻译为通常情况下G应该在P之前即GP是正确的顺序例外 1如果G在E之后则应该是PG顺序例外 2如果单词中包含PGUK序列发音为 X则应该是PG顺序注意规则中的GP和PG是指相邻字符对。大小写处理罗慕兰语的大小写规则不同大写字母可以出现在任何位置。因此比较时应忽略大小写但交换时应保留原始大小写。操作方式遍历字符串当遇到G且下一个字符是P时检查是否应该交换GP→PG如果G前面是E忽略大小写则不应交换已经是PG实际上是E G P时应为E P G需要仔细分析实际上规则说的是“G before P except after E”意思是正常情况下正确的顺序是GP如果G前面是E即序列E G则正确顺序应是PG即E P G因此当遇到GP时如果G前面是E则需要交换为PG否则保持GP当遇到PG时如果G前面是E则保持PG否则应交换为GP另外如果单词中包含PGUK则PG顺序是正确的。参考代码// Romulan Spelling// UVa ID: 373// Verdict: Accepted// Submission Date: 2016-07-31// UVa Run Time: 0.020s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intmain(intargc,char*argv[]){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);string line;while(getline(cin,line)){intlengthline.length();for(inti0;ilength;i){// 处理 G 与后面 P 的关系if(tolower(line[i])g){// 检查前面是否是 P即 PG 的情况if(i0tolower(line[i-1])p){// 检查是否因为 PGUK 而不应交换if(ilength-2tolower(line[i1])utolower(line[i2])k);// PGUK 例外不交换else{// 向左移动 G直到遇到不是 P 的字符intji;do{// 如果前面有 E则停止E 后的 PG 是正确的if(j1tolower(line[j-2])e)break;swap(line[j-1],line[j]);j--;}while(j0tolower(line[j-1])p);}}}// 处理 P 与后面 G 的关系if(tolower(line[i])g){if(ilength-1tolower(line[i1])p){// 如果前面有 E需要交换为 PGif(i0tolower(line[i-1])e)swap(line[i],line[i1]);// 如果后面是 PGUK 模式需要交换为 PGelseif(ilength-3tolower(line[i2])utolower(line[i3])k){swap(line[i],line[i1]);// 如果前面还有 G 且前面是 E继续交换if(i1tolower(line[i-1])gtolower(line[i-2])e)swap(line[i-1],line[i]);}}}}coutline\n;}return0;}