[算法摘要] 字符串散列

最编程 2024-05-03 15:07:33

...

字符串哈希

理论基础

字符串哈希/字符串编码是什么？
字符串编码是一种常用的字符匹配方法。一般地，一个字符串 s 的编码值计算公式如下：

网络异常，图片无法展示

其核心是将字符串看成一个 k 进制的整数，其中 k 是字符串中可能出现的字符种类，本题中字符串只包含小写字母，即 k = 26（也可以取比 k 大的整数，一般来说可以取一个质数，

例如 29 或 31）。这样做的好处是绕开了字符串操作，将字符串看成整数进行比较，并可以在常数时间内将字符串加入哈希集合中。

什么时候两个字符串相同？
当两个字符串的长度相同并且编码值也相等时，这两个字符串相同
如何预处理出不同长度字符的编码表示？

网络异常，图片无法展示

在实际编码中，当字符串的长度很长时，对应的哈希编码值也会很大，甚至会超出整数类型的范围。对此，一般的解决方法是对字符的编码值进行取模（MOD），使其保持在整数类型的范围之内。

哈希冲突：字符串哈希本身存在哈希冲突的可能，一般会在尝试131之后尝试使用13131 ，然后再尝试使用更大的质数。
base如何选择？
将字符串表示为一个 P 进制的数，P 是一个经验值，P = 131 / 13331/ 131313 不会出现哈希值冲突（概率很小，所以不考虑冲突）

相关题目

重复的DNA序列【LC187】

DNA序列 由一系列核苷酸组成，缩写为 'A', 'C', 'G' 和 'T'.。

例如，"ACGAATTCCG" 是一个 DNA序列 。

在研究 DNA 时，识别 DNA 中的重复序列非常有用。

给定一个表示 DNA序列 的字符串 s ，返回所有在 DNA 分子中出现不止一次的 长度为 10 的序列(子字符串)。你可以按 任意顺序 返回答案。

思路计算每个长度为10的子字符串的字符串哈希编码值，当遇到相同的哈希编码值时，将该字符串放入结果集中

注意：不严谨，未判断长度是否相同

实现

字符串哈希的「构造数组」和「计算哈希」的过程，不会溢出吗？

会溢出，溢出就会变为负数，当且仅当两个哈希值溢出程度与 Integer.MAX_VALUE 呈**不同【相同？】**的倍数关系时，会产生错误结果（哈希冲突），此时考虑修改或者采用表示范围更大的 long 来代替 int。->不取余也是可以的

溢出1->Integer.MIN_VALUE:-2147483648

class Solution {
    // private final static long MOD = 1000000007;
    public List<String> findRepeatedDnaSequences(String s) {
        int n = s.length();
        int base = 7;
        int[] h = new int[n + 1];
        int[] p = new int[n + 1];
        p[0] = 1;
        Map<Integer, Integer> count = new HashMap<>();
        List<String> res = new ArrayList<>();
        for (int i = 1; i <= n; i++){
            h[i] = h[i - 1] * base + s.charAt(i - 1);
            p[i] = p[i - 1] * base;
        }
        for (int i = 0; i <= n - 10; i++){
            int code = hash(h, p, i, i + 10 - 1);
            int cnt = count.getOrDefault(code, 0);
            if (cnt == 1){
                res.add(s.substring(i, i + 10));
            }
            count.put(code, cnt + 1);
        }
        return res;
    }
    private int hash(int[] h, int[] p, int l, int r){
        return h[r + 1] - h[l] * p[r - l + 1];
    }
}

网络异常，图片无法展示

class Solution {
    int N = (int)1e5+10, P = 131313;
    int[] h = new int[N], p = new int[N];
    public List<String> findRepeatedDnaSequences(String s) {
        int n = s.length();
        List<String> ans = new ArrayList<>();
        p[0] = 1;
        for (int i = 1; i <= n; i++) {
            h[i] = h[i - 1] * P + s.charAt(i - 1);
            p[i] = p[i - 1] * P;
        }
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 1; i + 10 - 1 <= n; i++) {
            int j = i + 10 - 1;
            int hash = h[j] - h[i - 1] * p[j - i + 1];
            int cnt = map.getOrDefault(hash, 0);
            if (cnt == 1) ans.add(s.substring(i - 1, i + 10 - 1));
            map.put(hash, cnt + 1);
        }
        return ans;
    }
}

作者：宫水三叶
链接：https://leetcode.cn/problems/repeated-dna-sequences/solutions/1035708/gong-shui-san-xie-yi-ti-shuang-jie-hua-d-30pg/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

不同的循环子字符串【LC1316】

给你一个字符串 text ，请你返回满足下述条件的不同非空子字符串的数目：

可以写成某个字符串与其自身相连接的形式（即，可以写为 a + a，其中 a 是某个字符串）。

例如，abcabc 就是 abc 和它自身连接形成的。

暴力

思路：
暴力枚举每个子字符串，判断其后是否有相同字符串，如果有那么将字符串记录在哈希表中，最后返回哈希表的大小
实现

class Solution {
    public int distinctEchoSubstrings(String text) {
        int n = text.length();
        Set<String> set = new HashSet<>();
        for (int i = 0; i < n; i++){
            for (int len = 1; 2 * len <= n - i; len++){
                if (text.substring(i, i + len).equals(text.substring(i + len, i + 2 * len))){
                    set.add(text.substring(i, i + len));
                }
            }
        }
        return set.size();

    }
}

网络异常，图片无法展示

字符串哈希

思路
通过字符串哈希将子字符串转化为long类型变量，降低放入哈希表的时间复杂度。

字符串哈希不再赘述，实现时只使用一个哈希表进行实现，未发生哈希冲突。保险起见可以使用n个哈希表实现

在「判断」这一步中，由于我们只对两个字符串进行比较，因此引入哈希冲突（在下方的注意事项中也有提及）的概率极小。然而在「去重」这一步中，最坏情况下字符串的数量为 O ( N 2 ) O(N^2)O(N

)，大量的字符串造成哈希冲突的概率极大。为了减少字符串的数量以降低冲突的概率，我们可以使用 N 个哈希集合，分别存放不同长度的字符串，即第 m 个哈希集合存放长度为 m + 1 的字符串的哈希值。这样每个哈希集合只对某一固定长度的字符串进行去重操作，并且其中最多只有 N 个字符串，冲突概率非常低。

作者：力扣官方题解

链接：https://leetcode.cn/problems/distinct-echo-substrings/solutions/101305/bu-tong-de-xun-huan-zi-zi-fu-chuan-by-leetcode-sol/

来源：力扣（LeetCode）

实现

class Solution {
    private final static long MOD = 1000000007;
    public int distinctEchoSubstrings(String text) {       
        int n = text.length();
        int base = 31, res = 0;
        long[] h = new long[n + 1], p = new long[n + 1];
        p[0] = 1L;
        for (int i = 1; i <= n; i++){
            h[i] = (h[i - 1] * base + text.charAt(i - 1)) % MOD;
            p[i] = p[i - 1] * base % MOD;
        }
        Set<Long> seen = new HashSet<>();
        for (int i = 0; i < n; i++){
            for (int len = 1; 2 * len <= n - i; len++){
                long hashLeft = hash(h, p, i, i + len - 1);
                if (!seen.contains(hashLeft) && hashLeft == hash(h, p, i + len, i + 2 * len - 1)){
                    res++;
                    seen.add(hashLeft);
                }
            }
        }
        return res;
    }
    private long hash(long[] h, long[] p, int l, int r){
        return (h[r + 1] - h[l] * p[r - l + 1] % MOD + MOD) % MOD;
    }
}

最长重复子串【LC1044】

给你一个字符串 s ，考虑其所有 重复子串 ：即 s 的（连续）子串，在 s 中出现 2 次或更多次。这些出现之间可能存在重叠。

返回 任意一个 可能具有最长长度的重复子串。如果 s 不含重复子串，那么答案为 "" 。

字符串哈希【超时】

字符串太长啦

class Solution {
    long[] h, p;
    public String longestDupSubstring(String s) {
        int n = s.length();
        this.h = new long[n + 1];
        this.p = new long[n + 1];
        p[0] = 1;
        int base = 1313131;
        Set<Long> set = new HashSet<>();
        int l = -1, r = -2;
        for (int i = 1; i <= n; i++){
            h[i] = h[i - 1] * base + s.charAt(i - 1);
            p[i] = p[i - 1] * base;
        }
        for (int i = 0; i < n; i++){
            for (int j = i; j < n; j++){
                long code = hash(i, j);
                if (set.contains(code) && j - i > r - l){
                    l = i;
                    r = j;
                }
                set.add(code);
            }
        }
        return l == -1 ? "" : s.substring(l, r + 1);

    }
    private long hash(int l, int r){
        return h[r + 1] - h[l] * p[r - l + 1];

    }
}

字符串哈希+二分答案

思路

二段性：题目要求得「能取得最大长度的任一方案」，首先以「最大长度」为分割点的数轴具有「二段性」：

小于等于最大长度方案均存在（考虑在最大长度方案上做删减）；
大于最大长度的方案不存在。

class Solution {
    long[] h, p;
    public String longestDupSubstring(String s) {

																				
						
							上一篇：							
								navicat 写 sql 怎么不运行以前的代码怎么办 - 掘金							
						
						
							下一篇：							
								odoo中ondelete的用法							
						
					
															
						
							推荐阅读						
						
														
								
									
										[算法摘要] 字符串散列									
								
							
														
								
									
										算法 - 散列 - 简单 - 两数之和									
								
							
														
								
									
										[ACWing] 841.字符串散列									
								
							
														
								
									
										RIPEMD 算法：多功能散列算法中的瑰宝									
								
							
														
								
									
										python 学习 - hashlib.md5 摘要算法（散列算法）									
								
							
														
								
									
										将 md5 和 sha1 用于字符串和文件散列等。									
								
							
														
								
									
										搞懂2018年10月11日的加密技术：对称加密、非对称加密与Hash算法，从此轻松应对加解密和散列函数那些事儿									
								
							
														
								
									
										用 PHP 的 md5 函数快速计算和加密字符串的 MD5 散列