P3370. 字符串哈希

发表于 2023-10-30 分类于洛谷阅读次数： Waline：本文字数： 197 阅读时长 ≈ 1 分钟

考点

哈希函数

题解

#include <bits/stdc++.h>
using namespace std;
const int LEN = 23333, P = 131;
string s;
vector<string> hsh[LEN];
int ans;

void f()
{
    int h = 0;
    for (int i = 0; i < (int)s.length(); ++i)
        h = (1ll * P * h + s[i]) % LEN;
    for (int i = 0; i < hsh[h].size(); ++i)
    {
        if (hsh[h][i] == s)
            return;
    }
    hsh[h].emplace_back(s);
    ++ans;
}

int main()
{
    int n;
    cin >> n;
    while (n--)
    {
        cin >> s;
        f();
    }
    cout << ans;
    return 0;
}