算法竞赛入门经典(第2版) 4-6UVa508 - Morse Mismatches

书上具体所有题目：http://pan.baidu.com/s/1hssH0KO 代码：（Accepted，10 ms）

//UVa508 - Morse Mismatches
#include<iostream>
#include<string>
#include<map>
using namespace std;
map<char, string> morse;
map<string, string> word;
string wo, tran, result;
char c;

int cmp(string a, string b) {
	if (a == b) return 0;
	if (a.size() > b.size()) a.swap(b);
	if (a == b.substr(0, a.size())) return b.size() - a.size();
	return 666;
}

int main()
{
	//freopen("in.txt", "r", stdin);
	//ios::sync_with_stdio(false);
	while ((cin >> c) && c != '*') cin >> morse[c];
	while ((cin >> wo) && wo[0] != '*') {
		auto cp = wo.begin();
		tran = morse[*cp];
		while (++cp != wo.end())
			tran += morse[*cp];
		word[wo] = tran;
	}
	while ((cin >> tran) && tran[0] != '*') {
		result.clear();
		int min = 888;
		for (auto i = word.begin();i != word.end();++i) {
			if (i->second == tran)//精确寻找
				if (!result.size() || *result.rbegin() == '?') result = i->first;
				else { result += "!";break; }
			else if (!result.size() || *result.rbegin() == '?') {//模糊寻找
				int n = cmp(tran, i->second);
				if (n<min) min = n, result = i->first + "?";
			}
		}
		cout << result << '\n';
	}
	return 0;
}

分析：思路是先根据电报代码表把单词全部转换成代码，单词和其代码存在一个map里，然后一个个检测下面的码的匹配。精确匹配不用说，如果只找到一个，直接输出，找到多个的话还是只输出第一个，但加一个“!”；模糊匹配是检索每个单词的代码，看哪一串缺的最多出来的代码最少 / 看VJ上好些0ms的，但我又想不出来什么更好的算法。想过会不会是循环的问题，于是试过将精确寻找和模糊寻找分开循环，结果还是10ms。就想到应该又是流的速度太慢导致。就加了一句ios::sync_with_stdio(false);关了stdio同步，果然变0ms了。唉好吧。。不过想了想不必太较真，博客里使用的还是没关同步的版本。 不用map也可以做的，map似乎还自带排序来着？我也是第一次用map，一开始做没用map，后来想试试看map，就改了。不过改成map后好像有些问题，主要是针对char[]字符串，因为char[]不可以用=来赋值，只能用strcpy()函数，而用这个函数给map赋值报错了，编译通不过，捣鼓半天不知道怎么改，就改用string了，慢一点但是方便。 好几天没刷题了，整个人懒洋洋的，脑子使不出劲，这题写了好久。。主要还是那win10那破一周年更新，导致显卡驱动不正常，折腾了好几天，题目落下了。虽然作为一个win10脑残粉，甚至在考虑要不要回win7. /