1

我试图使用 Rabin Karp 和二进制搜索编写一个最长的公共子字符串程序。为此，我编写了一个方法，该方法基本上为其中一个字符串创建哈希表，键是从索引 i 开始的长度为 M 的模式的哈希值。他们键的值将是索引 i 。

我写了以下代码：

#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) ;

}

问题是我无法将键插入到地图中。我收到以下错误，我对此毫无意义。任何人都可以帮助我理解这是什么？

错误 3 错误 C2664: 'std::pair<_Ty1,_Ty2> std::_Tree<_Traits>::insert(const std::pair<_Kty,_Ty> &)' : 无法将参数 1 从 'int' 转换为 ' const std::pair<_Ty1,_Ty2> &' c:\program files\microsoft visual studio 9.0\vc\include\xtree 760 SPOJ

错误 2 错误 C2100: 非法间接 c:\program files\microsoft visual studio 9.0\vc\include\xtree 760 SPOJ

4

3 回答 3

6

如果您尝试插入键值对，则需要插入一个std::pair<K, V>, whereK和V分别是键和值类型。见std::map:insert。你需要类似的东西

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

如果您想为给定键插入一个值，并且您不介意可能覆盖以前存在的值，您可以使用operator[]：

hashmap[newKey] = someValue;
于 2012-10-09T11:28:14.993 回答
2

从 C++11 开始，您还可以使用emplace(key, value). 这会使用给定的参数为您构造 a pair，然后将其插入到map.

hashmap.emplace(newKey, 0);
于 2016-06-15T00:20:07.777 回答
1

你应该打电话

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

insert als0 返回std::pair<iterator, bool>- 您可以检查result.second是否已成功插入元素（例如，如果存在具有相同 key 的元素，则不会插入它并返回 false。

于 2012-10-09T11:30:54.567 回答