Recongizing substrin using HashFunction

[MrProfit]

Hi, mates!
I'm trying to write a program to recognize a substring in a given string, using hashing. The common STL string methods doesnt work for me, because they are too slow.

unsigned long N = power(2,32)-1;
unsigned long d = 107;
unsigned int HashFunction(char* key)
{
     type result =0 ;
     int i=0;
     while(key[i])
     {
            result+= (power(d,i)*key[i++]) % N;
            cout<<result<<endl;
     }
     return result;
}
}

I don't know if my hash function is well written, its my first try. Can anybody suggest me how to continue recognising a substring using that function ?
Thank you in advance!
PS: the function "power" is equivalent with pow, but works for int.

[jsmith]

Yeah, I think the STL string methods are fast enough. It's your hash function that is terribly slow.

The first time through the loop you compute 107^0
The second time you compute 107^1
The third time you compute 107^2
etc.

Since your power function is probably just a loop, you have n^2 multiplies just in power() to hash a string of length n. You need to store an intermediate result so you don't have to compute it from scratch every time.

[MrProfit]

Yeah, i agree the power function is a stupid idea i gues...
I already tryed the STL string methods but i have a time limit for the task and they told me i have to use hashing to perform it faster. So hashing is really faster than string methods.

[jsmith]

This should do the same thing as your function but quite a bit faster:
(note: code assumes 32-bit unsigneds)

unsigned Hash( const char* key ) {
    unsigned result( 0 );
    unsigned pwr = 1;

    assert( key );
    for( i = 0; key[ i ]; ++i ) {
        result += pwr * key[ i ];
        pwr *= 107;
    }

    return result;
}

[Gumbercules]

My book gives this as an example of a simple hash function.

int hash = 0;
for (int i = 0; key[i]; ++i)
    hash = 31 * hash + key[i];

seems fast. I don't know how good it is as a hash function though.

[jsmith]

Determining the strength of hash functions is left to cryptologists. I'd recommend using one already out there such as SHA1, MD5, etc. (Be aware that both have been cracked though).

[MrProfit]

Thank you for the answers. May be you've heard about the Rabin-Karp algorithm. This is the best way to get the task done(i think).
http://www.eecs.harvard.edu/~ellard/Q-97/HTML/root/node43.html