## 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.

Point Value: 10
Time Limit: 1.00s
Memory Limit: 16M
Author: hansonw1

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

• (0/0)
is this directed to the C++/C users only?

• (0/0)
No. Figure out what the code does and then you can program it however you like, in whatever language you like.

• (0/0)
Well, figuring it out may not be so easy, some things are very different in C++ (for example, % is mod). However, this can be coded in any language, so maybe if you ask Hanson nicely, he'll translate it into Pascal for you.

• (4/0)
Well, here's my attempt at it.
It only compiles in Free Pascal.

``{\$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.``

• (0/6)
Is the scoring for this going to be based upon other people's code length?

• (4/0)
Does it say that anywhere?