【算法学习】字符串哈希(Hash) |
您所在的位置:网站首页 › 字符串英文单词是什么意思 › 【算法学习】字符串哈希(Hash) |
什么是字符串Hash 构造字符串Hash 1)自然溢出方法 2)单Hash方法 3)双Hash方法 4)三种不同的构造方法的对比 获取子串的Hash O(1) 1)例子 2)公式 具体的题目例子 1)题目链接 2)题意 3)解题分析 4)AC代码(自然溢出 C++) 5)AC代码(单Hash C++) 6)AC代码(双Hash C++) 什么是字符串Hashhash,其实就是将一个东西映射成另一个东西,类似Map,key对应value。 那么字符串Hash,其实就是:构造一个数字使之唯一代表一个字符串。但是为了将映射关系进行一一对应,也就是,一个字符串对应一个数字,那么一个数字也对应一个字符串。 用字符串Hash的目的是,我们如果要比较一个字符串,我们不直接比较字符串,而是比较它对应映射的数字,这样子就知道两个“子串”是否相等。从而达到,子串的Hash值的时间为 O(1),进而可以利用“空间换时间”来节省时间复杂的。
我们希望这个映射是一个单射,所以问题就是如何构造这个Hash函数,使得他们成为一个单射。不用担心,接下来的内容正要讲解。 构造字符串Hash假如给你一个数字1166,形式上你只知道它只是1和6的组合,但你知道它代表的实际大1*10^3+1*10^2+6*10^1+6*10^0。 同理,给你一个字符串,要把它转换为数字,就可以先把每一个字符都先对应一个数字,然后把它们按照顺序乘以进制(Base)的幂进行相加,然后这个数可能很大,所以一般会取余数(MOD)。 根据上面的理解,其实将字符串映射成数字,和我们平时的将一个 某Base进制数,变为一个十进制数,相类似。 我们先定义以下: 给定一个字符串 构造字符串Hash总共有三种方法。每一种方法,主要都是用使用 Base 和 MOD(都要求是素数),一般都是 Base < MOD,同时将Base和MOD尽量取大即可,这种情况下,冲突(即不同字符串却有着相同的hash值)的概率是很低的。 1)自然溢出方法对于自然溢出方法,我们定义 Base ,而MOD对于自然溢出方法,就是 unsigned long long 整数的自然溢出(相当于MOD 是 定义了上面的两个数组,首先 那么对应的 Hash 公式为: (类似十进制的表示,14,一开始是 0,然后 0 * 10 + 1 = 1,接着 1*10 + 4 = 14)。 2)单Hash方法 同样的,定义了 Base 和 MOD,有了对应的要求余 MOD。所以一般用 long long 就可以了。 #define ll long long ll Base; ll hash[MAXN], p[MAXN]; hash[0] = 0; p[0] = 1;定义了上面的两个数组,首先 那么对应的 Hash 公式为: 对于此种Hash方法,将Base和MOD尽量取大即可,这种情况下,冲突的概率是很低的。 举例 如取Base = 13,MOD=101,对字符串abc进行Hash hash[0] = 0 (相当于 0 字串) hash[1] = (hash[0] * 13 + 1) % 101 = 1 hash[2] = (hash[1] * 13 + 2) % 101 = 15 hash[3] = (hash[2] * 13 + 3) % 101 = 97 这样,我们就认为字符串abc当做97,即97就是abc 的hash值。 3)双Hash方法 用字符串Hash,最怕的就是,出现冲突的情况,即不同字符串却有着相同的hash值,这是我们不想看到的。所以为了降低冲突的概率,可以用双Hash方法。 将一个字符串用不同的Base和MOD,hash两次,将这两个结果用一个二元组表示,作为一个总的Hash结果。 相当于我们用不同的Base和MOD,进行两次 单Hash方法 操作,然后将得到的结果,变成一个二元组结果,这样子,我们要看一个字符串,就要同时对比两个 Hash 值,这样子出现冲突的概率就很低了。 那么对应的 Hash 公式为: 映射的Hash结果为: 这种Hash很安全。 4)三种不同的构造方法的对比 其实,自然溢出方法,说到底就是单Hash方法,只是把MOD变成了自动溢出,也就是 获取子串的Hash O(1) 上面我们得到的 Hash值都是前 i 个字符的字串,那么如果我们想获取 我们先以一个具体的例子来理解。 1)例子假设有一个 现在我们想求字串 不难发现,对应项系数只差一个
若已知一个 同时,Hash值是要进行取 MOD 的: 看起来这个式子人畜无害,但是对于取模运算要谨慎再谨慎,注意到括号里面是减法,即有可能是负数,故做如下的修正: 至此得到求子串hash值公式。 值得一提的是,如果需要反复对子串求解hash值,预处理Base的n次方效果更佳。所以才有上面用 具体的题目例子 1)题目链接 https://leetcode-cn.com/problems/distinct-echo-substrings/ 2)题意给你一个字符串 text ,请你返回满足下述条件的 不同 非空子字符串的数目: 可以写成某个字符串与其自身相连接的形式。例如,abcabc 就是 abc 和它自身连接形成的。 示例 1: 输入:text = "abcabcabc" 输出:3 解释:3 个子字符串分别为 "abcabc" , "bcabca" 和 "cabcab" 。示例 2: 输入:text = "leetcodeleetcode" 输出:2 解释:2 个子字符串为 "ee" 和 "leetcodeleetcode" 。提示: 1 |
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |