Rabin Karp 算法详解及Python实现

Rabin Karp 算法是用于实现字符串的模式匹配，先看leetcode上的28题，由此题的暴力解法引出Rabin Karp算法。

Leetcode 28. 实现strStr()
题目
给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回 -1 。
例
输入：haystack = “hello”, needle = “ll”
输出：2
暴力解法 遍历haystack中所有长度与needle相同的子串，依次进行比较。时间复杂度为O(nm)

class Solution():
    def strStr(self, haystack, needle):
        return self.bruteForce(haystack, needle)
        
    # 遍历haystack中长度与needle相同的子串，依次判断子串与needle是否相等
    def bruteForce(self, haystack, needle):
        n, m = len(haystack), len(needle)
        self.m = m

        for l in range(0, n-m+1):
            r = l + m
            if self.strEquals(haystack[l:r], needle):
                return True
        return False

    def strEquals(self, string1, string2):
        # 时间复杂度O(m)
        # return string1 == string2 的时间复杂度也是O(m)
        for i in range(self.m):
            if string1[i] != string2[i]:
                return False
        return True
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

一、Rabin Karp 核心思路

Rabin-Karp 是对 “所有长度为 len(needle) 的 haystack 子串 进行 strEquals” 这个步骤进行优化。
Rabin-Karp将符合长度要求的子串 和 needle 都做一个哈希映射，映射为数字，如果两个字符串的哈希映射值相等，再进行strEquals比较。
因为数字之间的比较时间复杂度为O(1)，我们假设在对haystack进行遍历的过程中，有k词子串的哈希映射值与needle相等，则时间复杂度是 O(n + km)，如果哈希映射做的好的，k可以等于1，此时复杂度为O(n+m)

class Solution():
    def strStr(self, haystack, needle):
        return self.rabinKarp(haystack, needle)
        
    # 遍历haystack中长度与needle相同的子串，依次判断子串与needle是否相等
    def rabinKarp(self, haystack, needle):
        n, m = len(haystack), len(needle)
        self.m = m
				
        for l in range(0, n-m+1):
            r = l + m
            if self.strHash(haystack[l:r]) == self.strHash(needle):
                if self.strEquals(haystack[l:r], needle):
                    return True
        return False

    def strEquals(self, string1, string2):
        # 时间复杂度O(m)
        # return string1 == string2 的时间复杂度也是O(m)
        for i in range(self.m):
            if string1[i] != string2[i]:
                return False
        return True
    def strHash(self, string):
    	pass
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

二、字符串如何做哈希映射

先看一个简单的问题，字母如何映射为数字？

# 字母转成数字，让 a = 1, 则其它字母为ch - 'a' + 1
chDigit = ord(ch) - ord('a') + 1
1
2

参考数字的b进制转十进制计算方式，将字符串看成是b进制的数，那字符串的哈希映射就是将b进制数转换为10进制数
$$\begin{gathered} text="llo" \\ text的哈希映射： \\ Htext=l\ast b^2+l\ast b^1+o\ast b^0 \end{gathered}$$
代码：

    def strHash(self, string):
        b = 131
        result = 0
        for ch in string:
            result = (ord(ch) - ord('a') + 1) + result * b
        return result
1
2
3
4
5
6

比如我们现在以b=26来进行计算，当遇到字符串过长时，会引起溢出的问题。

所以我们再做一层映射，对计算出的字符串做一个取模的操作，将Hneedle映射在[0, p-1]之间

因为取模之后，b再取26就容易产生哈希冲突了。可以将b调大，比如b = 131，p = 1e5+7

在运算过程中，我们对每个可能 > p的数值都做个%p的操作

    def strHash(self, string):
        b, p = 131, 1e5+7
        result = 0
        for ch in string:
            result = ((ord(ch) - ord('a') + 1) + result * b)%p
        return result
1
2
3
4
5
6

现在我们可以把内部的字符串对比，换成两个字符串转成Hash后，数字进行对比

def strStr(self, haystack, needle):
		n, m = len(haystack), len(needle)
  	for l in range(0, n-m+1):
    		r = l + m
    		if self.strHash(haystack[l:r]) == self.strHash(needle):
          	if self.strEquals(haystack[l:r], needle):
                return True
  	return False
  
    def strHash(self, string):
        b, p = 131, 1e5+7
        result = 0
        for ch in string:
            result = ((ord(ch) - ord('a') + 1) + result * b)%p
        return result
            
    def strEquals(self, string1, string2):
        # 时间复杂度O(m)
        # return string1 == string2 的时间复杂度也是O(m)
        for i in range(self.m):
            if string1[i] != string2[i]:
                return False
        return True
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

三、借助前缀和列表计算滑动窗口

Haystack[l:r]在计算的时候，可以借用前缀和列表preH，preH存haystack前i个字符的哈希值

# 以 haystack = hello 为例
preH[0] = 0
preH[1] = self.strHash("h")
preH[2] = self.strHash("he")
preH[3] = self.strHash("hel")
preH[4] = self.strHash("hell")
preH[5] = self.strHash("hello")

# 前缀列表的计算
# 为避免循环中preH[i-1]越界，preH多开一个，haystack在遍历的时候为对齐，把haystack[i]改为haystack[i-1]
preH = [0 for _ in range(n+1)]
for i in range(1, n+1):
		preH[i] = (preH[i-1]*b + (ord(haystack[i-1]) - ord('a') + 1))%p

# 滑动窗口的映射值计算
# 有了前缀哈希列表后，我们可以计算haystack中的任一滑动窗口的映射值
import math
# haystack = "hello"
# haystack[1:3] = "el"
# = preH[3] - preH[1] * b^(3-1) = "hel" - "h00" 
# 总结为公式: 
haystack[l:r] = preH[r] - preH[l] * math.pow(b, r-l)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

四、leetcode28. 代码实现

class Solution(object):
    def strStr(self, haystack, needle):
        """
        :type haystack: str
        :type needle: str
        :rtype: int
        """
        # 计算haystack的前缀哈希值
        b，p = 131, 1e5+7
        n, m = len(haystack), len(needle)

        # 计算needle的hash映射值，顺便把 b^m 通过遍历连乘出来
        Hneedle, bm = 0, 1
        for ch in needle:
            Hneedle = ((Hneedle * b) % p + (ord(ch) - ord('a') + 1)) % p
            bm = bm * b % p
            
        # 计算haystack的前缀哈希映射值列表
        preH = [0 for _ in range(n+1)]
        for i in range(1, n+1):
            preH[i] = ((preH[i-1]) * b % p + (ord(haystack[i-1]) - ord('a') + 1)) % p
        # 遍历计算haystack中长度为needle的窗口
        for l in range(n-m+1):
            r = l + m
            # preH[r] - (preH[l] * bm)%p 有可能是负值，再取模一次，映射在[1,p-1]中
            curr = ((preH[r] - (preH[l] * bm)%p))%p
            if curr == Hneedle and haystack[l:r] == needle:
                return l
        return -1

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