C ++的“map”容器是否对字符串的连续子串应用Rabin-Karp算法?

问题描述 投票:1回答:1

我正在研究代码抄袭检测方法。我需要使用指纹算法来实现这种方法。指纹算法将源代码的所有子字符串放入哈希表。 (所有子串都具有相同的长度。)出于优化的目的,建议在将指纹放入哈希表时使用Rabin-Karp算法。

例如;对于string = abcdef和length = 5,我们应该将abcde和bcdef子串放到哈希表中。由于字符串的散列需要对字符串的每个字符应用数学运算,因此对于许多子字符串来说它将是昂贵的。

Rabin-Karp算法利用连续的子串。它计算第一个指纹的哈希值。对于其余的子串,它使用前一个子串。

C ++的“map”容器是否会自动将此算法应用于后台的连续子串?或者我应该编写自己的哈希库?

c++ hash hashmap hashtable rabin-karp
1个回答
2
投票

std :: unordered_map http://www.cplusplus.com/reference/unordered_map/unordered_map/的构造函数需要一个哈希。

来自std :: hash(https://en.cppreference.com/w/cpp/utility/hash)上的在线文档:

实际的散列函数是依赖于实现的,除了上面指定的那些之外,不需要满足任何其他质量标准。

© www.soinside.com 2019 - 2024. All rights reserved.