Hashing
As a programmer for some large software company, you've been enlisted to make a "cryptographic hash" (a way of "uniquely" encoding a string so that it cannot be decoded).These hashes can be used for things such as passwords - you encrypt the password so that you can check whether two passwords are equal without ever knowing the passwords themselves.
Although many such algorithms already exist, your manager has decided to reinvent the wheel and make an entirely new algorithm.
Your co-workers have come up with the following code through much trial and error, but sadly it is far too slow for anything practical.
The code:
#include <iostream>
#include <string>
using namespace std;
unsigned int hash1(string s)
{
if (s == "") return 0;
unsigned int ret = 0;
for (int j = 1; j ≤ s.size(); j++)
for (int k = 0; k < j; k++)
ret = ret + s[k];
ret += hash1(s.substr(1));
return ret;
}
unsigned int hash2(string s, string t)
{
if (s == "") {
unsigned temp = 0;
for (int i = 0; i < t.size(); i++)
temp += t[i];
return temp;
}
unsigned ret = 0;
int index = hash1(s) % s.size();
char ch = s[index];
s.erase(index, 1);
ret += hash2(s, t);
ret += hash2(s, ch + t);
ret %= 2147483647;
return ret;
}
int main()
{
string s;
getline(cin, s);
unsigned int hash = hash1(s);
hash += hash2(s, "");
printf("%08X\n", hash);
return 0;
}
Your job is to optimize the code so that it can actually be usable for strings up to, say, length 1,000,000.
Your code must produce exactly the same output as the above code for any input.
All Submissions
Best Solutions
Point Value: 10
Time Limit: 1.00s
Memory Limit: 16M
Added: Feb 15, 2009
Author: hansonw1
Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3
Comments (Search)
Well, here's my attempt at it. It only compiles in Free Pascal. [code]{$H+} // use AnsiStrings; same length as C++ strings uses sysutils; var s: string; hash: SizeUInt; function hash1(s: string): SizeUInt; var ret, j, k: SizeUInt; begin if s = '' then begin hash1 := 0; exit; end; ret := 0; for j := 1 to length(s) do for k := 1 to j do inc(ret, ord(s[k])); inc(ret, hash1(copy(s, 2, length(s) - 1))); hash1 := ret; end; function hash2(s, t: string): SizeUInt; var temp, ret: SizeUInt; i, hash, idx: longint; ch: char; begin if s = '' then begin temp := 0; for i := 1 to length(t) do inc(temp, ord(t[i])); hash2 := temp; exit; end; ret := 0; idx := hash1(s) mod length(s); ch := s[idx]; delete(s, idx, 1); inc(ret, hash2(s, t)); inc(ret, hash2(s, ch + t)); ret := ret mod maxLongint; hash2 := ret; end; begin readln(s); hash := hash1(s); inc(hash, hash2(s, '')); writeln(intToHex(hash, 8)); end.[/code]It only compiles in Free Pascal.