P3370 【模板】字符串哈希——题解

解题思路

把每个字符串插入哈希集合。相同字符串只会在集合中保留一份，最终集合大小就是答案。为减少扩容开销，可以提前 reserve。

复杂度分析

设所有字符串总长度为 $L$，期望时间复杂度 $O(L)$，空间复杂度 $O(L)$。

C++17 参考代码

#include <bits/stdc++.h>
using namespace std;
int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n; cin>>n;
    unordered_set<string> s;
    s.reserve(n*2+10);
    string x;
    while(n--){cin>>x;s.insert(x);}
    cout<<s.size()<<'\n';
    return 0;
}

#include <bits/stdc++.h> using namespace std; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin>>n; unordered_set s; s.reserve(n*2+10); string x; while(n--){cin>>x;s.insert(x);} cout<<s.size()<<'\n'; return 0; }