C++

Forum

 
strings hashing

ahmad alghadban (19)
I am trying to check a substring if it's exist in another string
using string hashing.
This is my code.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
 
#include <bits/stdc++.h>

#define m 1000000007
#define N (int)2e6 + 3

using namespace std;

long long pows[N], h[N], h2[N];

set<int> ss;

int main()
{

    string s = "www.cplusplus.com/forum";

    // powers array
    pows[0] = 1;
    int n = s.length(), p = 31;
    for(int i = 1; i < n; i++){
        pows[i] = pows[i-1]*p;
        pows[i] %= m;
    }

    // hash from 0 to i array
    h[0] = s[0]-'a'+1;
    for(int i = 1; i < n; i++){
        h[i] = h[i-1] + (s[i]-'a'+1)*pows[i];
        h[i] %= m;
    }

    // storing each hash with 9 characters in a set
    ss.insert(h[8]);
    for(int i = 9; i < n; i++){
        int tp = h[i] - h[i-9]*pows[i-8];
        tp %= m;
        tp += m;
        tp %= m;
        ss.insert(tp);
    }

    // print hashes with 9 characters
    set<int>::iterator itr = ss.begin();
    while(itr != ss.end()){
        cout << *(itr++) << " ";
    }
    cout << endl;

    // t is the string that i want to check if it is exist in s
    string t = "cplusplus";
    int n2 = t.length();
    h2[0] = t[0]-'a'+1;
    for(int i = 1; i < n2; i++){
        h2[i] = h2[i-1] + (t[i]-'a'+1)*pows[i];
        h2[i] %= m;
    }
    // print t hash
    cout << h2[n2-1] << endl;

    return 0;
}


That code gives me a wrong result.
The hash of t should be one of the stored hashes in the set but it doesn't.
Is the wrong in way or in code or in powers or what ?
thanks in advance.

Last edited on
dhayden (5795)
The hash of t should be one of the stored hashes in the set.
Why? It's hard to know why the code isn't working when we don't know how it's supposed to work to begin with.

So tell us why the hash of t should be one of the stored hash values in ss.
thmm (703)
ahmad alghadban (19)
dhayden
the hash of t should be one of the stored hash because it's a substring of s
that's if the hashing way which i'm using is correct, but it isn't.
I discovered the wrong, but if you have any comment in my code till me.
ahmad alghadban (19)
learner2
Maybe :)
thank you
Topic archived. No new replies allowed.