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

HuangRuibo · 2025-04-12 07:32:56 · 题解

题解

P3370 【模板】字符串哈希

题目传送门

题目重述

我们有 N 个字符串，每个字符串都可能包含数字、大小写字母（注意大小写敏感哦！）。现在要统计这些字符串中有多少个是独一无二的。

比如输入：

5
abc
aaaa
abc
abcc
12345

输出应该是 4，因为有两个 "abc" 是重复的。

解题思路

暴力法？太慢啦！

最直接的想法是把所有字符串存下来，然后两两比较。但是当 N= 10000 时，比较次数会达到恐怖的 5000 万（10^7 \times 5）次！绝对会超时。

哈希表来拯救世界！

这时候就该我们的英雄 std::unordered_set 登场了！它就像一个有魔法的口袋：

1. 每次往里面放字符串时，魔法会自动检查是否已经存在

2. 如果已经存在，就悄悄忽略

3. 最后数一数口袋里的东西就知道有多少独特的字符串啦！

std::unordered_set 是什么？

什么是哈希表？

想象你有一堆玩具要整理：

• 普通箱子：要找一个玩具得从头翻到尾

• 魔法箱子：每个玩具有个专属编号，直接就能找到它的位置

哈希表就是这样的魔法箱子！

unordered_set 的魔法特性

• 自动去重：相同的元素只保留一个

• 无序但高效：不像 set 那样排序，所以速度更快

代码实现

#include<iostream>
#include<unordered_set>// 哈希表头文件
#include<string>
using namespace std;
int main()
{
    int N;
    cin>>N;
    unordered_set<string> str;// 定义哈希表
    for(int i=0;i<N;++i)
    {
        string s;
        cin>>s;
        str.insert(s);// 自动去重
    }
    cout<<str.size();// 独特元素数量就是答案
    return 0;
}

AC Record

为什么不用 set？

set 虽然也能去重，但它……

• 保持元素有序

而 unordered_set：

• 元素无序

对于本题，我们不需要顺序，只要去重，所以 unordered_set 更合适！