题解 | 字符串哈希

C++ 将字符串映射为一个整数，采用基本多项式哈希

#include <iostream>
#include <string>
#include <vector>
using namespace std;

// 基本多项式哈希 - 将字符串映射为一个整数
class PolynomialHash {
  private:
    unsigned long long base = 911382629;
    unsigned long long mod = 1000000000000000003ULL;
    vector<unsigned long long> hashes;
  public:
    unsigned long long getHash(string s) const {
        unsigned long long hash = 0;
        for (char c : s) {
            hash = (hash * base + static_cast<unsigned long long>(c)) % mod;
            // static_cast<unsigned long long>(c) 将char转换为ull
            // 虽然不太理解，但是这是关键，可以直接背下来
        }
        return hash;
    }
    bool isInHash(unsigned long long hash) const {
        for (unsigned long long h: hashes) {
            if (h==hash) return true;
        }
        return false;
    }
    void insert(string s) {
        unsigned long long hash;
        hash = getHash(s);
        if (!isInHash(hash)) {
            hashes.push_back(hash);
        }
    }
    int getSize() {
        return hashes.size();
    }
};

int main() {
    int n;
    PolynomialHash H;
    string s;
    cin >> n;
    while (n--) {
        cin >> s;
        H.insert(s);
    }
    cout << H.getSize() << endl;
}
// 64 位输出请用 printf("%lld")

直接使用c++ unordered_set<string>

#include <iostream>
#include <string>
#include <unordered_set>
using namespace std;

int main() {
    int n;
    unordered_set<string> H;
    string s;
    cin >> n;
    while (n--) {
        cin >> s;
        H.insert(s);
    }
    cout << H.size() << endl;
}
// 64 位输出请用 printf("%lld")