算法竞赛入门经典(第2版) 5-5UVa10391 - Compound Words

题意：问在一个词典里，那些单词是复合词，即哪些单词是由两个单词拼出来的。

---

渣渣代码：（Accepted， 30ms）

//UVa10391 - Compound Words
#include<iostream>
#include<string>
#include<set>
using namespace std;
set<string> dic;
int main()
{
	//freopen("in.txt", "r", stdin);
	string w;
	while (cin >> w) dic.insert(w);
	for (const auto &r : dic) {
		int s = r.size();
		for (int i = 1;i < s;++i) {
			if (dic.count(r.substr(0, i)) && dic.count(r.substr(i, s - i))) {
				cout << r << '\n';
				break;
			}
		}
	}
	return 0;
}

分析：遍历两遍词典找出两个单词来找/判断复合词肯定不行，慢死了，肯定只能是拆当前单词拆成两部分，枚举所有可拆分的情况，看这两部分有没有找到两个独立的单词。于是用了如上面的超简单的方法，但是30ms。学习他们的0ms至10ms的做法，发现他们都用了hash。我不知道什么是hash，一下子看他们代码也看的一愣一愣的。看了一下午代码和hash资料了，累死了。。明天继续改进这题，今天我要歇息下了。明天再会更新此博客。

更新：对hash还不熟，但是自己做了一下，但是总是Runtime error！我要哭了，自己做了N组不同的测试数据，没有任何异常，但是提交总是RE！为什么啊！！！！：

垃圾代码：（Runtime Error， --）

//UVa10391 - Compound Words
#include<cstdio>
#include<cstring>
const int mdic = 120200, d[] = { 4616,177,7 };
char dic[mdic][40];

int hash(char* s) {
	int re = 0;
	for (int i = 0;s[i] && i < 3;++i)
		re = (s[i] - 'a')*d[i];
	return re;
}
bool find(char* s) {
	int h = hash(s);
	while (strcmp(s, dic[h]) > 0) ++h;
	if (strcmp(s, dic[h])) return 0;
	return 1;
}

int main()
{
	freopen("in.txt", "r", stdin);
	memset(*dic, 0, sizeof(*dic));
	char w[40], (*p)[40] = dic;
	while (scanf("%s", w) != -1) {
		int h = hash(w);
		while (dic[h][0]) ++h;
		strcpy(dic[h], w);
	}
	for (int I = 0;I < mdic;++I, ++p) {
		if (!*p) continue;
		int len = strlen(*p);
		for (int i = 1;i < len;++i) {
			char a[40], b[40];
			strncpy(a, *p, i);a[i] = 0;
			strcpy(b, *p + i);
			if (find(a) && find(b)) printf("%s\n", *p);
		}
	}
	return 0;
}

分析：尽量按照自己的想法做的。对于获得hash那个函数，我也是自己想的（4616=120010/26，177=120010/26/26，7=120010/26/26/26），不知道高人有什么看法。还有再次声明：这个代码是RE的！！我测试了好多数据都没问题，一到oj上就RE。。好歹来个WA啊啊啊（哇的一声就哭了） 就我自己的测试数据，上面的版本用时2136，下面的4726。。。。怎么还慢了。。不服。。以后学精了再说吧。