MinimalPerfectHashFinder.cpp

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>

using namespace std;
const int MaxCharacterHash = 20;
int searchMinimalPerfectHash(int i, vector<string>& fwords, vector<string>& hash, vector<bool>& visited, vector<int>& values );
vector<string> words = {
	"auto",
	"break",
	"case",
	"char",
	"const",
	"continue",
	"default",
	"do",
	"double",
	"else",
	"enum",
	"extern",
	"float",
	"for",
	"goto",
	"if",
	"int",
	"long",
	"register",
	"return",
	"short",
	"signed",
	"sizeof",
	"static",
	"struct",
	"switch",
	"typedef",
	"union",
	"unsigned",
	"void",
	"volatile",
	"while"
};
bool comparator(pair<char,int> a, pair<char,int> b){
	return a.second > b.second;
}
bool comparator2(pair<string,int> a, pair<string,int> b){
	return a.second > b.second;
}
inline int toInt(char c){
	return c - 'a';
}
int getFrequency(vector<pair<char,int>> frequency, char c ){
	for(auto f:frequency){
		if( f.first == c )
			return f.second;
	}
}
void sortByAlphabet(vector<pair<char,int>>& frequency){
	for(int i=0;i<26;i++){
		frequency.push_back( make_pair((char)(i+'a'),0) );
	}
	for(auto word:words){
		frequency[ toInt(word.front()) ].second++;
		frequency[ toInt(word.back())].second++;
	}
	sort(frequency.begin(),frequency.end(),comparator);
}
void sortByPriority(vector<pair<char,int>>& frequency,vector<string>& fwords){
	vector<pair<string,int>> pwords;
	for(auto word:words){
		int priority = getFrequency(frequency,word.front()) + getFrequency(frequency, word.back());
		pwords.push_back(make_pair(word,priority));
	}
	sort(pwords.begin(),pwords.end(),comparator2);
	fwords.resize(pwords.size());
	transform(pwords.begin(),pwords.end(),fwords.begin(),[](pair<string,int> pw){ return pw.first; });
}
inline int hashValue(string word, vector<int>& values){
	const int HashShift = 2;
	return values[toInt(word.front())]+values[toInt(word.back())]+word.size() - HashShift;
}
int selectHash(int ch, int i, vector<string>& fwords, vector<string>& hash, vector<bool>& visited, vector<int>& values ){
	for(int v=0; v < MaxCharacterHash; ++v){
			values[ch] = v;
			visited[ch] = true;
			if(searchMinimalPerfectHash(i, fwords, hash, visited, values))
				return 1;
	}
	return 0;
}
int searchMinimalPerfectHash(int i, vector<string>& fwords, vector<string>& hash, vector<bool>& visited, vector<int>& values ){
	if( i == fwords.size() )
		return 1;
	int front = toInt(fwords[i].front());
	int back  = toInt(fwords[i].back());
	if( visited[ front ] && visited[ back ] ){
		if( !hash[ hashValue(fwords[i], values) ].empty() )
			return searchMinimalPerfectHash(i+1, fwords, hash, visited, values);
		else
			return 0;
	}
	else if(!visited[ front ]){
		return selectHash(front, i, fwords, hash, visited, values);
	}
	else if(!visited[ back ]){
		return selectHash(back, i, fwords, hash, visited, values);
	}
}
int main() {
	vector<pair<char,int>> frequency;
	vector<string> fwords;

	sortByAlphabet(frequency);
	sortByPriority(frequency,fwords);
	
	vector<bool> visited(frequency.size(),false);
	vector<int> values(frequency.size(),0);
	vector<string> hash(fwords.size(),string(""));
	if(searchMinimalPerfectHash(0, fwords, hash, visited,values)){
		for(auto word:hash){
			cout<< word <<endl;
		}
	}
	else{
		cout<< "Fail" << endl;
	}
	
	return 0;
}
/*

e: 9
t: 7
d: 6
s: 6
c: 5
f: 5
r: 5
n: 3
o: 3
g: 2
v: 2
i: 2
u: 2
b: 1
w: 1
m: 1
l: 1
k: 1
h: 1
a: 1
p: 0
q: 0
j: 0
x: 0
y: 0
z: 0
*/