字符串哈希思路非常简单 但具体实现细节比较非常麻烦
C++等有unsigned long long 类型的语言实现起来是最容易的 因为不用取模 靠unsigned long long自然溢出 就能得出正确的结果 而其他语言在这个取模上要注意很多
当然由于字符串哈希这个算法本身泛用性很好 而且可以简化很多问题 背一背相关细节还是值得的
下面就以python为例给出模板 以及正确的模值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# 这个MOD 值 可以保证最终答案是正确的
MOD = 10**13 + 7
P = 131
n = len(s)
h = (n + 1) * [0]
p = (n + 1) * [0]
# 这里一定要注意 这个初值一定要给 !!!
p[0] = 1
for i in range(1,n + 1):
    h[i] = (h[i - 1] * P % MOD + ord(s[i])) % MOD
    p[i] = p[i - 1] * P % MOD

def get(l,r):
    return (h[r] - h[l - 1] *  p[r - l + 1] % MOD) % MOD

经典例题总结
难度值4:字符串哈希与其他算法的结合
三等分
对字母串可执行的最大删除数

例1

三等分
原题链接:
https://leetcode.cn/problems/three-equal-parts/submissions/

使用字符串哈希来迅速判断 字符串之间的值是否相等
从而将时间复杂度从O(n^3) 降到 O(n^2)
但是这样还是不够 题目给出的范围是3x10^4
所以在结合 哈希 先将[1,l] 即第一段的范围全部记录在哈希表 然后枚举r 从而将时间复杂度降到O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution:
    def threeEqualParts(self, arr: List[int]) -> List[int]:
        c = sum(arr)
        if c == 0:
            return [0,len(arr) - 1]
        if c % 3:
            return [-1,-1]
        MOD = 10**13 + 7
        P = 131
        n = len(arr)
        h = (n+1) * [0]
        p = (n+1) * [0]
        p[0] = 1

        for i in range(1,n + 1):
            h[i] = (h[i-1] * P % MOD + arr[i - 1] ) % MOD
            p[i] = p[i-1] * P % MOD 

        def get(l,r):
            #print(l,r)
            return (h[r] - h[l - 1] * p[r - l + 1] %MOD) % MOD
        
        d = defaultdict(int) 
        
        # 先算O(n) 算出所有 1~l 的值
        # 然后O(n) 枚举 r 比较结果得出答案
        for l in range(1,n+1):
            #print("-----")
            d[get(1,l)] = l
        
        for r in range(n,0,-1):
            #print("xxxx")
            if get(r,n) in d:
                l = d[get(r,n)]
                if get(l+1,r-1) == get(r,n):
                    return [l-1,r-1]
        return [-1,-1]

例2

对字母串可执行的最大删除数
原题链接:
https://leetcode.cn/problems/maximum-deletions-on-a-string/
通过字符串哈希来判断字符串之间是否相等 将复杂度从O(n^3) 降到O(n^2)
然后 动态规划 从后往前 判断当前字符段是否两端相同的情况 然后更新答案
另外这题用python写 是过不了的 一个原因是因为python本身性能差 另外这题python定义不了unsigned long long 必须手动取模 也就是使用上面的模板 所以计算量会翻很多 (但也应该是线性的翻… 最后没过就离谱) 所以这里就展示go的代码 看来以后不能老是偷懒写python了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
package main

type ULL = uint64

func max(a int,b int)int{
	if a > b{
		return a 
	}
	return b
}

func deleteString(s string) int {
	n := len(s)
	p := make([]ULL, n+1)
	h := make([]ULL, n+1)
	p[0] = 1
	var P ULL = 131
	for i := 1; i <= n; i++ {
		h[i] = h[i-1]*P + ULL(s[i-1])
		p[i] = p[i-1] * P
	}

	f := make([]int, n+1)
	
	get := func (l int,r int) ULL {
		return h[r] - h[l-1]*p[r-l+1]
	}

	for i := n; i >= 1; i-- {
		f[i] = 1
		for j := 1; j <= (n-i + 1)/2 ; j++ {
			if get(i,i+j-1) == get(i+j,i+2*j-1){
				f[i] = max(f[i],f[i+j] + 1)
			}
		}
	}

	return f[1]
}