关于算法:编码KR字符串匹配一个简单到领导都看得懂的算法

“ 常怀感恩，生存或者就不会处处深渊。”

这几天看了《柔性字符串匹配》，觉得很有意思。书是好书，只是这个脑子是不是猪脑就不晓得了，于是秉着知之为知之，不知为不知的精力，我筹备再次去求教一下我的领导，在一个月黑风高的夜晚，我给领导发了个音讯，领导这么回复了我。

—

**KR 算法
**

话说回来，咱们明天要说的这个字符串匹配算法比之前讲过的 kmp，horspool，sunday 简略的多的字符串匹配算法，咱们晓得暴力匹配是通过对两个字符串进行每一个地位字符比照来查找匹配的上的子字符串。明天说的这个 KR 算法的思维和暴力匹配有些许相似，不过在实现上做了一些改良，这也是为什么说这个算法非常容易了解的起因，因为思路十分间接。

在计算机科学中，Rabin–Karp 算法或 Karp–Rabin 算法（英文：Rabin–Karp algorithm 或 Karp–Rabin algorithm），是一种由理查德·卡普与迈克尔·拉宾于 1987 年提出的、应用散列函数以在文本中搜查单个模式串的字符串搜索算法单次匹配。该算法先应用旋转哈希以疾速筛出无奈与给定串匹配的文本地位，尔后对残余地位是否胜利匹配进行测验。此算法可推广到用于在文本搜查单个模式串的所有匹配或在文本中搜查多个模式串的匹配。

维基百科

依照常规，对于被匹配的字符串称之为齐全字符串，用于查找匹配的字符串称为为模式字符串。KR 算法是通过计算散列值的形式从齐全字符串中进行模式字符串的匹配，也就是咱们常常说的哈希值。

KR 从齐全字符串的首位开始，计算和模式字符串长度统一的子字符串的哈希值，再通过哈希值与模式字符串计算失去的哈希值进行比拟，如果哈希值不存在则字符串肯定不相等。如果哈希值相等，两个字符串可能相等，这个时候就须要通过遍历比照两个字符串的每个字符，如果所有程序字符都相等的话，则两个字符串相等。

为什么哈希值相等，然而值不肯定相等，这里波及到一个概念就是哈希碰撞，理解的童鞋间接跳过，不理解的童鞋听我举个例子，一年有 365 天，如果这个时候一个房间里有 366 集体，那么是不是肯定会有两个人的生日的同一天，尽管生日雷同，然而不是同一个人，其实哈希能够看成是固定长度的函数，而理论长度大于这个固定长度，所以值会重合，当然这个例子不是特地的精确，感兴趣的童鞋能够维基或者百度更精确的定义。

因而当两个长度一样的字符串计算出的哈希值统一的时候，还须要比对字符串对应地位上的所有字符，因而能够很简略的得出 KR 算法的实现代码。

func KarpRabinMatch(allString, modeString string) int {
  // 计算模式字符串的哈希值
  hashMode := hash(modeString)
  // 下标匹配完结
  end:= len(allString)-len(modeString)+1
  for i := 0; i < end ; i++ {
    // 计算子字符串的哈希值
    hashKey := hash(allString[i : i+len(modeString)+1])
    if hashMode == hashKey {for j := 0; j < len(modeString); j++ {if allString[i+j] != modeString[j] {break}
      }
      return i
    }
  }
  return -1
}

能够看到代码中对模式字符串哈希值（hashMode）的计算只会解决一次，在循环中，从齐全字符串的第一个字符开始的子字符串，计算对应哈希值，判断该哈希值与 hashMode 比拟，如果不相等往后一位计算下一个子字符串的哈希值。

只有哈希值相等的状况下才会比照模式字符串的每一个字符，所以抉择一个好的哈希函数，会使比拟模式字符串每个字符的操作变得非常少，因而这个算法的工夫复杂度在计算子字符串的哈希值上。如果子字符串的每个字符都要参加计算，齐全字符串的所有字符须要计算长度 n 遍，每遍须要计算模式字符串的长度 m 个字符，因而工夫复杂度为 O(mn)。

—

旋转哈希

如上所说，如果每一次都要对子字符串的每个字符都进行计算，那么工夫复杂度会达到 O(mn), 如果想要升高工夫复杂度（提速），须要找到一种哈希形式，缩小每次哈希计算的次数。于是针对这个字符串匹配算法，设计了一种简略的然而不优良的哈希函数计算形式：旋转哈希。

旋转哈希（也称为滚动哈希、递归哈希、滚动校验和或滑动哈希）是一种哈希函数，输出的内容在一个窗口中进行挪动哈希。

多数哈希函数容许疾速计算滚动哈希值 — 只给出旧的哈希值，新的哈希值被疾速计算出来，旧的值从窗口中移除，新的值增加到窗口中 — 相似于挪动均匀函数的计算形式，比其余低通滤波器更快。

维基百科

旋转哈希的想法很简略，有点相似窗口挪动，每次向右挪动窗口，把退出窗口的最右边字符的哈希值减掉，并且加上新退出窗口的最左边字符的哈希值，这样就达到了每次通过常数工夫计算出哈希值。

如下所示，子字符串 ABB 的哈希值，hash1 = A + B + B，当窗口挪动到 BBE 这个子字符串的时候，子字符串 BBE 的哈希值 hash3 = hash1 – A + E 即可。

然而依照加法的这种形式去实现旋转哈希，产生哈希碰撞的概率十分高，比如说 ABB 和 BBA 的哈希值是一样的。这样就会导致不一样的字符串的哈希值相等，须要比拟每一个字符，工夫复杂度变高。

—

Rabin 指纹

咱们曾经确定通过旋转哈希来实现 KR 算法，那么有什么更好的旋转哈希的计算形式可能产生更少的碰撞。这里要说的就是迈克尔·拉宾提出的 Rabin 指纹。

维基百科

Rabin 指纹是通过程序解释多项式，通过以后字符串的多项式值，在窗口挪动的时候，校验计算新的子字符串的后果值。它能够利用在一些分块数据的校验上，比如说网络传输包的校验和等。

—

多项式散列

计算哈希函数，如果模式字符串长度较长，通过多项式进行计算，可能会呈现哈希值超过机器反对长度的状况，所以这边须要进行取余，简略来说就是在保障散列尽量均匀散布的同时，不让长度溢出。

首先须要理解求余的个性：同余定理，在百度百科或者维基百科都能够找到对应的内容，其中有一条在咱们的计算中会应用到，也就是：

同余式相乘：若 a≡b(mod m)，c≡d(mod m)，则 ac≡bd(mod m)

假如字符集大小为 x，用质数 y 进行取模操作，用多项式散列进行哈希计算的表达式为：

即假如以后字符串字符集大小为 256，能够设置 x = 256，质数 y = 101 来计算（当然设置其余数值也能够），比如说齐全字符串为 abcd，而匹配字符串长度为 3。

首先计算子字符串 abc 的哈希值（字母通过 ASCI 码计算），即

而后字符串窗口挪动，计算 bcde 的哈希值，即

能够发现下面的两个哈希公式是减掉第一位的 a 的哈希值，而后再加上最初一位 a 的哈希值，通过旋转哈希的形式来实现常数工夫内哈希值的计算。

比照下面两个公式，会发现 hash（abcd）中 a 的哈希值和上面计算减掉 a 的哈希值相差一个 %101，依据下面的同余式相乘公式能够失去，后果是统一的。

—

写在最初

KR 算法尽管在单字符串的匹配中，算不上优良的算法，然而如果在字符串中查找 N 个对应的模式，即多模式搜寻中，KR 算法的变种 AC 自动机的效率十分高。

本文波及到的代码比拟少，很多比拟谨严的文字也是援用维基百科下面的解释，只是用了一些图片来诠释解决的过程。全文旨在阐明一种思路和计算形式（旋转哈希），兴许在之后工作中的某些场景会有所利用。

【往期回顾】

编码：震惊，让领导差点脑溢血的字符串匹配算法 KMP

编码：horspool 字符串匹配，折磨学生又来了

编码：sunday 字符串匹配，“欢快”的一天又开始了

编码：Lumuto 划分，实现疾速抉择

编码：前缀树工具

【参考资料】

https://zh.wikipedia.org/wiki…