| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
已亥年端午节清晨,哈希表1A留念#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
typedef unsigned long long ull;
typedef pair<ull, int> P1;
int N;
vector<P1> Hash_Table;
char input[30000][51];
const ull base = 31;
vector<int> Bucket[30000];
bool Comp_Vec(vector<int> a, vector<int> b){
if(a.size() == b.size()){
if(strcmp(input[a[0]], input[b[0]]) < 0){
return true;
} else {
return false;
}
}
return a.size() > b.size();
}
bool Comp_P1(P1 a, P1 b) {
if(a.first == b.first) {
if(strcmp(input[a.second], input[b.second]) < 0) {
return true;
} else {
return false;
}
}
return a.first < b.first;
}
ull get_hash_code(char * s) {
ull res = 0;
int ctr[26];
memset(ctr, 0, sizeof(ctr));
int L = strlen(s);
for(int i = 0; i < L; i ++) {
ctr[s[i] - 'a'] ++;
}
for(int i = 0; i < 26; i++) {
res = res * base + ctr[i];
}
return res;
}
int main() {
N = 0;
while(~scanf("%s", input[N])) {
ull hashcode = get_hash_code(input[N]);
Hash_Table.push_back(make_pair(hashcode, N));
N ++;
}
sort(Hash_Table.begin(), Hash_Table.end(), Comp_P1);
int M = -1;
ull prev;
for(int i = 0; i < N; i ++) {
if(i == 0 || Hash_Table[i].first != prev) {
M ++;
prev = Hash_Table[i].first;
}
Bucket[M].push_back(Hash_Table[i].second);
}
M++;
sort(Bucket, Bucket + M, Comp_Vec);
for(int i = 0; i < min(5, M); i ++){
printf("Group of size %d: ", Bucket[i].size());
for(int j =0; j < Bucket[i].size(); j ++){
if(j != 0 && strcmp(input[Bucket[i][j]], input[Bucket[i][j - 1]]) == 0){
continue;
}
printf("%s ", input[Bucket[i][j]]);
}
printf(".\n");
}
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator