字符串匹配(hash算法）

谁借莪１个温暖的怀抱￠ 2023-06-01 06:12 6阅读 0赞

# 字符串匹配(hash算法） #

[转载][Link 1]  
hash函数对大家来说不陌生吧 ？

而这次我们就用hash函数来实现字符串匹配。

首先我们会想一下二进制数。

对于任意一个二进制数，我们将它化为10进制的数的方法如下（以二进制数1101101为例）：  
![727740-20150914125030617-1862920123.png][]  
hash用的也是一样的原理，为每一个前缀（也可以后缀，笔者习惯1 base，所以喜欢用前缀来计算，Hash\[i\] = Hash\[i - 1\] \* x + si。  
![727740-20150914125847773-1413523264.png][]

一般地，  
而对于l - r区间的hash值，则为：  
![727740-20150914132038086-1449317622.png][]

但是如果n很大呢？那样不是会溢出了吗？

因此我们把hash值储存在unsigned long long里面， 那样溢出时，会自动取余2的64次方，but这样可能会使2个不同串的哈希值相同，但这样的概率极低（不排除你的运气不好）。

因此我们可以通过Hash值来比较两个字符串是否相等。

给出多项式hash的处理：

typedef unsigned long long ull; const int N = 100000 + 5; const ull base = 163; char s[N]; ull hash[N]; void init(){//处理hash值 p[0] = 1; hash[0] = 0; int n = strlen(s + 1); for(int i = 1; i <=100000; i ++)p[i] =p[i-1] * base; for(int i = 1; i <= n; i ++)hash[i] = hash[i - 1] * base + (s[i] - 'a'); } ull get(int l, int r, ull g[]){//取出g里l - r里面的字符串的hash值 return g[r] - g[l - 1] * p[r - l + 1]; }

转载于:https://www.cnblogs.com/tttfu/p/11340671.html

[Link 1]: https://www.cnblogs.com/zyf0163/p/4806951.html
[727740-20150914125030617-1862920123.png]: /images/20230601/2bf1778e628f43d3b164ba5231a50e49.png
[727740-20150914125847773-1413523264.png]: /images/20230601/8a2d1ec2d63b4cde9f81e54fd4e1ff59.png
[727740-20150914132038086-1449317622.png]: /images/20230601/ff7e072db23047c9a6f63515f091c39f.png

发表评论取消回复

表情：

评论列表（有 0 条评论，6人围观）

还没有评论，来说两句吧...

相关阅读

相关字符串匹配算法

目录 BF KMP next数组匹配代码 SunDay B

叁歲伎倆/ 2023年07月21日 14:29/ 0 赞/ 45 阅读

相关算法：字符串匹配算法：KMP算法

字符串匹配算法暴力算法BF算法，利用哈希值进行比较的RK算法，以及尽量减少比较次数的BM算法 ![在这里插入图片描述][20200301172159346.png]

小鱼儿/ 2023年07月10日 08:45/ 0 赞/ 52 阅读

相关算法 - KMP算法(字符串匹配)

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

本是古典何须时尚/ 2023年07月03日 10:47/ 0 赞/ 16 阅读

相关字符串匹配算法

主要算法：BF RK BM KMP Sunday算法 BF ：Brute Force，暴力匹配算法字符串A中查找字符串B 主串：A，长度n 模式串：B，长度m

女爷i/ 2023年06月23日 02:56/ 0 赞/ 156 阅读

相关字符串匹配(hash算法）

字符串匹配(hash算法） [转载][Link 1] hash函数对大家来说不陌生吧？而这次我们就用hash函数来实现字符串匹配。首先我们会想一下二进制数。

谁借莪１个温暖的怀抱￠/ 2023年06月01日 06:12/ 0 赞/ 7 阅读

相关字符串hash算法比较

<table> <tbody> <tr> <td>链表<font>查找</font>的时间效率为O(N)，二分法为log2N，B+ Tree为log2N

向右看齐/ 2022年08月24日 05:17/ 0 赞/ 175 阅读

相关字符串匹配算法

字符串匹配算法本文转自：[Yushneng][Yushneng] ：[http://blog.rainy.im/2016/04/24/string-find/][h

╰半夏微凉°/ 2022年08月21日 08:42/ 0 赞/ 183 阅读

相关字符串匹配算法

记录两个字符串匹配算法：KMP和BM算法。转载地址：http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%

╰+攻爆jí腚メ/ 2022年06月16日 09:27/ 0 赞/ 225 阅读

相关字符串匹配算法

BF算法（Brute Force）暴力匹配算法，在主串和模式串每次比较都只前进一个位置，进行比较。 ![18721752-e54c845998d33231.png][

电玩女神/ 2021年10月01日 09:16/ 0 赞/ 433 阅读

相关 Hash字符串匹配

hash字符串匹配即把固定长度的字符串转化为hash值进行匹配，这种匹配方式在大量数据的情况下是有误差的，大约万分之四五左右，这是因为hash值是通过字符和公式计算出来的，不同

╰+哭是因爲堅強的太久メ/ 2021年09月23日 01:14/ 0 赞/ 427 阅读