1
votes

I was attempting to write a Longest Common Substring program using Rabin Karp and Binary search. For that I wrote a method which basically create a hash table for one of the strings and the key would be the hash value of the pattern of length M starting at index i . The value of they key would be index i .

I have written the following code :

#include <iostream>
#include <string>
#include<map>
#include<math.h>
#define BASE 10
#define BASE2 10.0
#define M 99999989
using namespace std;
map<int, int> hashmap;
 int pHash=0;
 int mod(int a, int b) {
    return (a%b + b)%b;
}
 int getHash(string & pattern) {
     int hashVal = 0;
    for ( int i =0 ; i<pattern.length();i++) {
            int val = (int) pattern[i];
            hashVal = mod(hashVal*BASE + val, M);

    }

    return hashVal;
}
int rabinKarp(string &pattern, string & text)
{
     pHash = getHash(pattern);  
     cout<<"P HASH  : "<<pHash<<endl;
     int m = pattern.size();
     int fHash = getHash(text.substr(0, pattern.size()));
    int  newKey = fHash;
     hashmap.insert(newKey, 0);
     if(fHash==pHash)
            cout<<"Rabin Karp found a match at index : 0 "<< endl;


     for(int i = 1; i <=text.size()-pattern.size();i++) {
        int val = (int)text[i-1];
        double sz = (double)pattern.size()-1.0;
        int temp = pow(BASE2, sz);
        int mult= mod(temp,M);
        fHash = mod(fHash - mod(val*mult,M),M);
        fHash= mod(fHash*BASE, M);
        fHash= mod(fHash+(int)text[i+m-1], M);
        int key = fHash ;
        hashmap.insert(key, i);
        if(fHash==pHash)
            cout<<"Rabin Karp found a match at index : "<< i<<endl;
    }
    return 1;

}
int main() {
    string pattern;
    string text;
    cout<<"Please enter the pattern "<<endl;
    getline(cin, pattern) ;
    cout<<"Please enter the text " <<endl;
    getline(cin, text);
    int index = rabinKarp(pattern, text) ;

}

The problem is that I am unable to insert the keys into the map . I am getting the following error of which I can make no sense . Anyone can help me understand what this is ?

Error 3 error C2664: 'std::pair<_Ty1,_Ty2> std::_Tree<_Traits>::insert(const std::pair<_Kty,_Ty> &)' : cannot convert parameter 1 from 'int' to 'const std::pair<_Ty1,_Ty2> &' c:\program files\microsoft visual studio 9.0\vc\include\xtree 760 SPOJ

Error 2 error C2100: illegal indirection c:\program files\microsoft visual studio 9.0\vc\include\xtree 760 SPOJ

3
You have to create pair<int,int> instead of inserting 2 int. e.g. insert(pair<int,int>(newKey,0))nhahtdh
The compiler error makes perfect sense. It's telling you exactly what the problem is. You just need to learn to read them.John Dibling

3 Answers

6
votes

If you are trying to insert a key-value pair, you need to insert an std::pair<K, V>, where K and V are the key and value types respectively. See std::map:insert. You need something like

hashmap.insert(std::make_pair(newKey, 0));

If you want to insert a value for a given key, and you don't mind about potentially overwriting a previously existing value, you can use operator[]:

hashmap[newKey] = someValue;
2
votes

Since C++11, you can also use emplace(key, value). This constructs a pair for you using the given arguments, and then inserts it into the map.

hashmap.emplace(newKey, 0);
1
votes

You should call

 result = hashmap.insert(map<int, int>::value_type (newKey, 0)); 
 // or
 result = hashmap.insert(std::make_pair(newKey, 0));

insert als0 returns std::pair<iterator, bool> - you can check with result.second if you have successfully inserted the element (for instance if there were element with the same key , it would not insert it and return false.