题解 UVA508 【摩尔斯密码 Morse Mismatches】
这个题当把细节理解清楚了以后，其实很简单，就是因为自己题意理解不清，对题目的曲解太大了，所以才会拖延了这么长时间，看来以后需要耐心仔细地读英文题了。。。这题的意思是给定一些莫尔斯编码，给定一些已知字典，给定一些编码，求解这些编码的对应原文，如果可以精确匹配，则直接输出原单词，如果有多个可精确匹配的结果，则输出匹配结果里字典序最小的单词（紫书上说输出任意一个，这是错误的）并在末位加上“!”；如果无法精确匹配，则可以在编码的末尾增加或删除一些字符后匹配单词（增删应尽量小，就是找到增删最少的模糊匹配），无论增删后匹配一个还是多个，最后都要加上“？”，如果有多个模糊匹配结果（增删数相等），则输出字典序最小的匹配结果；如果无精确匹配也无模糊匹配结果，则输出整个给定字典里字典序最小的那个单词。
实现方面，看网上标程是用映射写的（也难怪自己没发现字典序这个关键词，映射里的元素直接就是排好序的，用映射看来很简单啊。。。= =），我用的是简单的字符数组，一个用来存给定的莫尔斯电码，一个结构体包含两个字符数组，一个存给定单词明文，并存下按莫尔斯电码翻译后的密文，重载小于运算，使字典按字典序排好，对于每个给定的编码，匹配字典里所有单词的密文，判断精确匹配的个数，若为0则开始模糊匹配，代码如下:
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
struct text{
char Plaintext[20];//明文
char Ciphertext[100];//密文
bool operator < (const text a)const{
return strcmp(Plaintext,a.Plaintext)<0;//重载小于运算，将给定字典元素按字典序排序
}
}str[101];
char morse[128][10],code[101];//morse存储摩尔斯码，code存储待解编码
int n=0;
int toMatch(int &p);//传入p的引用，获得匹配数并使p指向匹配位置
int main(){
ios::sync_with_stdio(false);
char c;
while(cin>>c,c!='*')//输入摩尔斯码
cin>>morse[(int)c];
while(cin>>str[n].Plaintext,str[n].Plaintext[0]!='*'){//输入给定字典元素
int len=strlen(str[n].Plaintext);
str[n].Ciphertext[0]=0;
for(int i=0;i<len;i++)//将给定字典元素按摩尔斯码翻译成密文存储
strcat(str[n].Ciphertext,morse[(int)str[n].Plaintext[i]]);
n++;
}
sort(str,str+n);//按字典序排序
while(cin>>code,code[0]!='*'){
int p,cont=toMatch(p);//获得匹配数量
if(cont)
cout<<str[p].Plaintext<<(cont==1?"":"!")<<endl;//多个精确匹配要额外输出叹号
else{
int minn=10000,pi=-1,lencode=strlen(code);
for(int i=0;i<n;i++){//模糊匹配时，遍历字典集
int len=strlen(str[i].Ciphertext);
if(lencode>len&&(strstr(code,str[i].Ciphertext)==code){//如果字典里某元素是待解编码的子串，且匹配位置为待解编码首字符，说明该字典元素可由待解编码删减字符得到
if((lencode-len)<minn){//要求删减数量尽量少
minn=lencode-len;
pi=i;
}
}
else if(lencode<len&&(strstr(str[i].Ciphertext,code)==str[i].Ciphertext)){//如果待解编码是字典里某元素的子串，且匹配位置为字典某元素的字符，说明该字典元素可由待解编码增加字符得到
if((len-lencode)<minn){//要求增加数量尽量少
minn=len-lencode;
pi=i;
}
}
}
if(pi==-1)//若模糊匹配也无任何结果，则输出字典序最小的元素并加问号
cout<<str[0].Plaintext<<"?"<<endl;
else//可匹配则输出，并且末尾加问号
cout<<str[pi].Plaintext<<"?"<<endl;
}
}
return 0;
}
int toMatch(int &p){
int cont=0;
for(int i=0;i<n;i++)
if(!strcmp(code,str[i].Ciphertext)){
if(!cont)//匹配时输出字典序靠前的，所以p指向第一个匹配的就OK
p=i;
cont++;
}
return cont;//返回精确匹配的个数
}