洛谷P3370 && 字符串哈希讲解
字符串哈希
寻找长度为n的主串s中的的匹配串T(长度为m)出现的位置或者次数问题属于字符串匹配问题。
朴素(一般)的想法就是从一个字符串的头开始for循环查找,当查找的一个字符与匹配串首字符相同时,往后查找长度为匹配串长度的字符串并一一比对,如果都一样的话,那么答案就加一;
但是往往有些题数据复杂度不允许这么干,于是我们引入字符串哈希这种操作;
具体流程:
滚动哈希,是优化复杂度的核心;
对于一个字符串的哈希值,我们定义哈希函数为H(C)=(c1b^m-1=c2b^m-2....+cmb^0)mod h,
说明:C为一个字符串名称,它由c1c2c3...cm组成,也就是C=c1c2c3c4....cm,其中m为C的长度;
b和h为互质的两个数(b<h),
也就是我们可以把一个字符串看成一个b进制的数(把‘A’看成1,把‘B’看成2...),因为10进制数(such as1234)可以表示成为1*10^3+2*10^2+3*10^1+4,在这里把10换成b就是b进制数的表示方式;因为字符串哈希形成的数可能很大所以要对原数进行取模h。
很多神仙心中可能会有疑问:取模后即使是不同的字符串他们的哈希值也可能相等,那么不同的字符串会有可能得出相同的哈希值,这样答案不就出错了吗?
答案是有可能的。算法错误?!
但是我们可以将可能性降到几乎忽略不计!
因为 仔细想想,是取模运算使哈希拥有了这种可能,只有取到h和b的公倍数时,哈希值才会相等,
但是我们把最小公倍数搞的很大,不就取不到了吗?
那么首先b和h要满足互质,在相近大小下使公倍数尽可能大,然后有意识调高b和h的值,
如果分别去h=1e9+7,b=1e9+9的话,他们最小公倍数就为(1e9+7)*(1e9+9),哈希值相同概率为1/(1e9+7)*(1e9+9),小到没朋友;
(可惜还是有毒瘤小伙伴出毒瘤数据坑害蒟蒻们。。)
不管了。。反正算法就是这样;
在代码实现中,h不必专门取1e9+7后再进行手动缩小操作,只要利用unsigned无符号整形的自然溢出特性,即可实现;
ok!
安利一个关于scanf读入字符串的小知识:
代码:
#include<cstdio>
#include<algorithm>
#include<cstring>
#define b 97//97是个质数,你也可以取的更大!
using namespace std;
int n,a[],ans=;//ans初始值为1,因为后面在判断时会少一个
char s[];
inline long long hash(char s[]){
int lenc=strlen(s+);
unsigned long long sum[];
sum[]=;
for(int i=;i<=lenc;i++)
sum[i]=sum[i-]*b+(unsigned)(s[i]-'');//哈希值求法
return sum[lenc];
}
int main(){
scanf("%d",&n);
for(int i=;i<=n;i++)
{
scanf("%s",s+);
a[i]=hash(s);//对于每一个字符串求哈希值
}
sort(a+,a++n);
for(int i=;i<=n;i++)
if(a[i]!=a[i-])ans++;
printf("%d",ans);
return ;
}
还有一个惨痛教训:
这是b开成7后碰到了那极小概率的惨痛经历。。。
而且测试点太大无法下载。。。
完结。。
最新文章
- 将博客搬至CSDN
- Composer使用
- 《Node.js开发实战详解》学习笔记
- [Shell]字符截取命令:cut, printf, awk, sed
- FZU 2214 Knapsack problem 01背包变形
- ASP.NET MVC 学习7、为Model Class的字段添加验证属性(validation attribuate)
- 分析一下FastDFS_java_client中TestClient.java这个文件以及跟它关联的这条线
- 【Linux】理解setuid()、setgid()和sticky位
- Gradle学习之使用java plugin
- C#中的关键字
- nginx的yum安装,基本参数使用,编译参数说明和Nginx基本配置,模块安装
- css实现半圆和圆
- 差异基因分析:fold change(差异倍数), P-value(差异的显著性)
- eclipse 启动tomcat 出现错误Could not publish server configuration: null. java.lang.NullPointerException
- [C#源代码]使用SCPI指令对通信端口(RS232/USB/GPIB/LAN)进行仪器编程
- os_cpu_a.asm
- js 字符串匹配
- 2018.06.29 NOIP模拟 区间(前缀和差量)
- PHP的cURL快速入门 (小偷采集程序)
- Codeforces 603E Pastoral Oddities