首页 > 代码库 > POJ 2945 Find the Clones Hash

POJ 2945 Find the Clones Hash

题目大意:给出一些字符串,问其中n个一样的有多少。


思路:看discuss里各种神奇的方法啊,什么map啊,什么Trie啊。这题不是一眼Hash么。。难道是我想错了?

任意hash方法将所有字符串hash然后排序,之后统计一下相同的有多少就行了,500+MS水过。。

PS:明天就是NOIP我这么水真的好(


CODE:

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define MAX 20010
#define BASE 13
using namespace std;

int points,length;
char s[30];
unsigned long long hash[MAX];
int ans[MAX];

inline unsigned long long GetHash(char *s)
{
	unsigned long long re = 0;
	for(int i = 1; i <= length; ++i)
		re = re * BASE + s[i];
	return re;
}

inline void Initialize()
{
	memset(ans,0,sizeof(ans));
}

int main()
{
	//ios::sync_with_stdio(false);
	while(scanf("%d%d",&points,&length),points + length) {
		Initialize();
		for(int i = 1; i <= points; ++i) {
			scanf("%s",s + 1);
			hash[i] = GetHash(s);
		}
		sort(hash + 1,hash + points + 1);
		int start = 1;
		for(int i = 1; i <= points; ++i)
			if(hash[i] != hash[start]) {
				++ans[i - start];
				start = i;
			}
		++ans[points - start + 1];
		for(int i = 1; i <= points; ++i)
			printf("%d\n",ans[i]);
	}
	return 0;
}


POJ 2945 Find the Clones Hash