【C++算法模板】字符串哈希，超详细注释带例题 |
您所在的位置：网站首页 › ccf常用算法模板 › 【C++算法模板】字符串哈希，超详细注释带例题 |
【C++算法模板】字符串哈希，超详细注释带例题
|
文章目录
0）概述1）数据结构2）求字符串哈希值3）求字符串字串的哈希值4）判断两个子串是否相同【例题】洛谷 P3370
视频链接：F02 字符串哈希 bilibili 0）概述 字符串哈希即把不同的字符串映射成不同的整数把字符串映射成一个 p p p 进制数字，对于一个长度为 n n n 的字符串 s s s 定义其 H a s h Hash Hash 函数为： h ( s ) = ∑ i = 1 n s [ i ] × p i − 1 ( m o d M ) h(s)=\sum_{i=1}^n s[i]×p^{i-1}(mod M) h(s)=∑i=1ns[i]×pi−1(modM)如：字符串 a b c abc abc ，哈希函数值为 a p 2 + b p 1 + c = 97 × 13 1 2 + 98 × 13 1 1 + 99 ap^2+bp^1+c=97×131^2+98×131^1+99 ap2+bp1+c=97×1312+98×1311+99如果两个字符串不一样但 H a s h Hash Hash 函数值一样，这样的现象被称作哈希碰撞 解决哈希碰撞的方法（极大程度减少哈希碰撞次数，但还是有可能碰撞） 巧妙设置 p p p 和 M M M 的值，保证 p p p 和 M M M 互质 p p p 通常为： 131 131 131 或 13331 13331 13331 M M M 通常取大整数 2 64 2^{64} 264，把哈希函数值 h h h 定义为 U L L ULL ULL，对于无符号数，超过则自动溢出，等价于取模了 1）数据结构 const int N=1e5+5; // 最大字符串的个数 const int M=1.5e3+10; // 题目中字符串的最大长度 const int P=131; // 131,13331不容易哈希碰撞 // p[i]:表示p的i次方 // h[i]:表示s[1~i]的哈希值,如h[2]表示字符串s前两个字符组成字符串的哈希值 ULL p[N],h[N]; char s[M]; // 存储字符串 int n; 2）求字符串哈希值 求一个字符串的哈希值相当于求前缀和
|
【本文地址】
今日新闻 |
推荐新闻 |