在刷题 / 比赛时经常会遇到判重的问题, 那么这次就来讲一讲字符串上的判重问题.
▎哈希是什么
判重我们通常会想到什么? 小编首先想到的是桶排序, 这种排序正是用了哈希的方法, 其实把哈希理解为一堆桶更合适.
比如说现在给你一堆数字, 让你判断一共有几种数字(也就是重复出现的不算): 1 5 4 1 1 3 5 6 . 以哈希的思想来解决就是这样的:
放若干个桶, 每个桶代表一种数, 遇到相应的数字就放进去, 判断几种数字就转换成了判断有几个有东西的桶就可以了.
那么, 接下来思考一个问题: 怎么存这些桶? 要存这些桶只要用绝对不可能重复出现的量来代表桶的序号, 例如...... 数组下标! 我们可以利用数组下标来当做桶, 每个桶里面东西的个数就是对应数组元素的值. 比如说用一个叫做 a 的数组来存这些桶, 当遇到数字 3 时, 只要将 a[ 3 ] ++; 就可以了.
其实这就是哈希, 所以说理解成一堆桶更形象.
▎字符串下的哈希
看到这里, 你一定会想, 字符串哈希有什么好讲的? 不也是一个道理吗? 当然不行! 仔细想想, 数组下标怎么存储成字符串呢? 数组下标都是整数的啊!
此时出路就很敞亮了, 我们可以把字符串转换成整数处理!
还记得吗? 在最开始学习时还学过 ASCII 码, 我们可以通过强制转换替换成整数.
可是问题又来了, 如何用 ASCII 表示字符串? 例如 AB, 其中 A 的 ASCII 码是 65,B 的 ASCII 码是 66.
1)用加的: AB 表示为 65+66=131. 反例: BA 表示为 66+65=131, 可 AB 和 BA 不一样;
2)用减的, 乘的, 除的, 似乎都同上, 表示出的值都不唯一;
3)放在一起: AB 表示为 6566, 这样的确举不出什么反例了, 但是数字的值变大了, 同时也区分不回去了, 6566 究竟是 6 和 566 呢? 还是 6,56 和 6 呢? 似乎不知道原来的字符串长什么样了.
自然而然, 我们便想到了转进制, 这样不易发生问题. 那么取什么样的进制会不发生或少发生问题呢? 我们往往会取 27,233,19260817 等等, 具体会视情况而定.(稍后会有例题讲解).
有时会超出 unsigned long long 的范围, 那该怎么办呢? 那么我们就要用取模的方法了, 通常会模一个很大的质数, 模多少可以看看题后的数据规模是多大.
有些时候会发生一些情况, 比如 3%2=1,5%2=1(打个比方, 一般模数不会这么小), 所以两个数取模后当成了一个数来处理, 这便叫做哈希冲突, 在做题时要减少这种冲突的产生.
▎例题 --[模板] 字符串哈希
题目描述
如题, 给定 N 个字符串(第 i 个字符串长度为 Mi, 字符串内包含数字, 大小写字母, 大小写敏感), 请求出 N 个字符串中共有多少个不同的字符串.
输入输出格式
输入格式:
第一行包含一个整数 N, 为字符串的个数.
接下来 N 行每行包含一个字符串, 为所提供的字符串.
输出格式:
输出包含一行, 包含一个整数, 为不同的字符串个数.
输入输出样例
输入样例 #1:
- 5
- abc
- aaaa
- abc
- abcc
- 12345
输出样例 #1:
4
说明
时空限制: 1000ms,128M
数据规模:
对于 30% 的数据: N<=10,Mi≈6,Mmax<=15;
对于 70% 的数据: N<=1000,Mi≈100,Mmax<=150
对于 100% 的数据: N<=10000,Mi≈1000,Mmax<=1500
样例说明:
样例中第一个字符串 (abc) 和第三个字符串 (abc) 是一样的, 所以所提供字符串的集合为{aaaa,abc,abcc,12345}, 故共计 4 个不同的字符串.
这道题完全是模板题, 直接套思路就好了.
▎Code speaks louder than words!
话不多说, 直接上代码(详见注释)
- #include<iostream>
- #include<algorithm>
- using namespace std;
- string s;int n;int hash[10000],mod=19270817,k=30,ans=1;
- int Hash(string str)
- {
- int len=str.length();
- int value=0;
- for(int i=0;i<len;i++)
- value=value*k+((int)str[i]-96);// 转进制
- return value;// 这里其实也可以模一下, 不过数据规模没有那么大
- }
- int main()
- {
- cin>>n;
- for(int i=1;i<=n;i++)
- {
- cin>>s;
- hash[i]=Hash(s);// 存储每个字符串转换后的哈希值
- }
- sort(hash+1,hash+n+1);// 排序, 目的是为了排除相同哈希值的字符串
- for(int i=2;i<=n;i++)
- if(hash[i]!=hash[i-1]) ans++;// 如果哈希值不同, 那么两个字符串就不一样
- cout<<ans;
- return 0;
- }
▎map 是啥?
说来对于这种题来说还有一大利器 --map. 简单介绍一下:
1)头文件:#include<map>
2)定义: map < 类型 , 类型> 变量名;
第一个类型是数组下标的类型, 第二个变量是数组值的类型
3)用处: map 定义出来的东西可以理解为数组下标为任意的数组, 这恰恰起到了刚才那道题最开始思路的效果
4)举个栗子: 比如说要定义一个数组下标是字符串的整型数组 s, 可以这么写 map<string , int> s;
怎么解刚才那道题? 直接普通哈希就可以了, 就不写注释了.
- #include<iostream>
- #include<map>
- using namespace std;
- map<string,int>s;string str[100000];int n,ans;
- int main()
- {
- cin>>n;
- for(int i=1;i<=n;i++)
- {
- cin>>str[i];
- s[str[i]]=1;
- }
- for(int i=1;i<=n;i++)
- {
- if(s[str[i]]==1)
- {
- ans++;
- s[str[i]]=0;
- }
- }
- cout<<ans;
- return 0;
- }
▎为什么放着 map 不用而用前一种方法
map 看起来好用, 就像数组一样, 其实 map 只是单单的映射, 简单来说就是暴力查询, 时间复杂度可想而知, 这速度很慢, 有时是可以 AC 题目的, 但有时是满足不了题目的要求的时间的, 所以还是老老实实用字符串下的哈希吧.
来源: https://www.cnblogs.com/TFLS-gzr/p/10927097.html