TIP

本文主要是介绍 RK(Rabin-Karp)算法 。

• Rabin-Karp算法（简称RK算法）
  • 算法分析
  • 详细分析
  • Rabin-Karp算法优势
• 参考文章

Rabin-Karp算法（简称RK算法）

Rabin-Karp算法的思路是将字符串的比较转换成数字的比较。比较两个长度为m的字符串是否相等需要O(m)的时间，而比较两个数字是否相等通常可以是Ɵ(1)。为了将字符串映射到对应的数字，故此需要用到哈希函数。我们都知道开放寻址法的哈希函数(open addressing)是可能遇到冲突的。对于这个问题来说冲突意味着虽然两个字符串的哈希值是一样的，但是这两个字符串实际上是不一样的。解决的办法是当遇到哈希值相同时，再做m次(模式P的长度为m)遍历，近一步判断这两个字符串是否相等。既是说，哈希值是第一步地判断，如果两个字符串不相等那么他们的哈希值也肯定不相等。通过第一步的筛选后，再做近一步更可靠的筛选。运气好的话，大部分不匹配的字符串会在第一步(通过哈希值)被筛选掉，仅留有少量的字符串需要近一步的审查。

python3

def rabin_karp(T, P):
    n = len(T)
    m = len(P)
    h1 = hash(P)
    for s in range(0, n-m+1):
        h2 = hash(T[s:s+m])
        if h1 != h2:
            continue
        else:
            k = 0
            for i in range(0, m):
                if T[s+i] != P[i]:
                    break
                else:
                    k += 1
            if k == m:
                print(s)

算法分析

从代码上来看Rabin-Karp算法与朴素算法十分近似，最坏情况下，每一个哈希值都冲突，而且对每个冲突都进行了m次的比较。在这种情况下，该算法的时间复杂度与朴素算法相同，如果算上哈希算法的开销，时间复杂度还要高出朴素算法（通常一个字符串进行哈希的算法的时间复杂度是Ɵ(1)）。当然这是最坏情况下的分析，对于平均情况下Rabin-Karp算法的效果要好得多。根据数学推断，Rabin-Karp算法的平均情况下的时间复杂度是O(n+m)。

详细分析

以下这一段分析Rabin-Karp的平均复杂度。如果不关心O(n+m)具体是如何得来的可以跳过这一段。 我们称两个字符串哈希值相同为一次命中，如果这两个字符串实际上是不同的则这次命中是一个伪命中。我们期望伪命中的次数要少一些，因为越少的伪命中意味着算法的效率越高。伪命中问题实际上是哈希算法的冲突问题，因此具体冲突的次数与具体的哈希算法相关。

算法导论中给出的哈希算法是： t[s+1] = (d * (t[s]-T[s+1]) * h) + T[s+m+1]) mod q

该算法是将字符串的每一个位的字符转换成对应的数字，再根据一定的权重相乘得到一个数值，最后对q取模映射到[0, q-1]空间的一个值。有n个数字待映射到[0, q-1]这q个值中。如果一个哈希函数把一个数字随机地映射到q个数中的任意一个，理论上来说冲突的个数O(n/q)。假设正确命中的个数是v，由前面讨论伪命中的个数是n/q。那么Rabin-Karp算法的期望运行时间是：O(n)+O(m(v+n/q))。如果有效命中v=O(1)并且q≥n，那么Rabin-Karp算法的时间复杂度是O(n+m)。

Rabin-Karp算法优势

Rabin-Karp算法的优势是可以多维度或者多模式的匹配字符串。以多模式匹配为例，如果需要在文本T中找出模式集合P=[P1, P2, ...Pk]中所有出现的模式。对于这个问题，Rabin-Karp算法的威力就能发挥出来了，Rabin-Karp算法能通过简单地扩展便能够支持多模式的匹配。

参考文章

• https://www.cnblogs.com/gaochundong/p/string_matching.html
• https://www.cnblogs.com/magic-sea/tag/%E5%AD%97%E7%AC%A6%E4%B8%B2%E5%8C%B9%E9%85%8D%E7%AE%97%E6%B3%95/
• https://zhuanlan.zhihu.com/p/93429400