POJ-2945: Find the Clones

keyword

ハッシュ　C++

問題概要

長さM(<20)のA,T,G,Cからなる文字列がN(<20000)個与えられる。個数の分布を求める問題。

解法

テストケースが多いらしく、TLEと戦わなければいけない。mapに突っ込んでいけばO(M*N*log N)で解けるけど、mapは定数が重いので落ちる。vectorに突っ込んでソートする方法でも(vectorをreserveしたにも関わらず)落ちた。これはソートするときにMがかかるのがいけないので、文字列を整数にencodeしてやる。ここで32bitのハッシュを使ったら無事通ったのだけど、よく考えると32bitじゃsqrt(2^32)=2^16なので衝突の可能性が割とあった。では64bitにすればよいかと言うと、そもそも文字列の種類が4^20しかないのでそれもうハッシュ値使う意味がない。最初から4進数だと思ってencodeしてやればよかった。計算量O(N*(M+log N))。ちなみにTrie使ったら実際に早くなるかどうかはさておき計算量は落とせる。実装時間14分。

#include <cstdio>
#include <vector>
#include <string.h>
#include <string>
#include <algorithm>
using namespace std;

const int MAX_N = 20009;
const int MAX_M = 23;
const unsigned int P = 1000000007;
int N, M;
int ans[MAX_N];
unsigned int ps[MAX_M];

inline unsigned int hash_func(char buf[]){
	unsigned int ret = 0;
	for(int i=0; i<M; i++){
		ret += buf[i] * ps[i];
	}
	return ret;
}

void proc(){
	char buf[30];
	vector<unsigned int> ws;
	ws.reserve(N+1);
	for(int i=0; i<N; i++){
		scanf("%s ",buf);
		ws.push_back(hash_func(buf));
	}
	sort(ws.begin(), ws.end());
	ws.push_back(0);
	memset(ans, 0, sizeof(ans));
	int cur = 0;
	for(int i=0; i<N; i++){
		if(ws[i] != ws[i+1]){
			ans[cur]++;
			cur = 0;
		}
		else{
			cur++;
		}
	}
	for(int i=0; i<N; i++){
		printf("%d\n",ans[i]);
	}
}

int main(){
	ps[0] = 1;
	for(int i=1; i<MAX_M; i++){
		ps[i] = ps[i-1] * P;
	}
	while(scanf("%d%d ", &N, &M), (N||M)){
		proc();
	}
	return 0;
}