32 | 字符串匹配基础（上）：如何借助哈希算法实现高效字符串匹配？

精选留言(105)

• 

  Jerry银银

  觉得今天的hash算法真是巧妙

  2018-12-05

   4

   89
• 

  ZX

  RK算法，在对主串构建的时候，就对比是不是一样的，一样就不继续计算后面的hash，这样会不会更快一点

  作者回复: 你说的很对 代码实现就是这样处理的

  2018-12-06

  

   51
• 

  P@tricK

  思考题：
  假设二维主串和模式串的维度分别是 m*n 和 i*j，横向在[0, m-i]，纵向在[0, n-j]取起始点，然后取同样的子串窗口对比，共有(m-i+1)*(n-j+1)个子串。
  
  ps：
  文中计算子串哈希值h[i]的公式中，第二个h[i-1]和后面的h[i+m-1]，应该是主串中的第i-1个和第i+m-1个字符的哈希值…

  2018-12-05

  

   21
• 

  Smallfly

  思考题：
  
  以模式串矩阵的大小，去匹配主串矩阵，每个小矩阵可以构建成字符串，就能用 RK 算法做字符串匹配了。
  
  如果主串的大小是 M * N，模式串大小为 m * n，则时间复杂度为 (M - m + 1) * (N - n + 1)。

  2018-12-05

   1

   17
• 

  Flash

  看了很多评论后，发现思考题其实就是举一反三，我们可以在比较时，将二维串矩阵看作是字符串来处理，至于怎么转换成一维字符串，应该有很多方法，比如子串矩阵和模式串矩阵都用同样的规则来组成一个字符串，从左到右，再从上到下遍历取矩阵的元素a[i][j]。转换为一维字符后，就可以用BF或者RK算法了 。
  复杂度分析，假设二维主串矩阵和模式串矩阵的维度分别是 m*n 和 i*j，按一个个矩阵来看子串的话，共有(m-i+1) * (n-j+1)个子串矩阵。
  用RK算法的话，复杂度就是O((m-i+1) * (n-j+1))。

  2019-01-27

   1

   12
• 

  Alan

  h[i] = 26*(h[i-1]-26^(m-1)*h[i-1]) + h[i+m-1];
  
  其中, h[i]、h[i-1] 分别对应 s[i] 和 s[i-1] 两个子串的哈希值
  ------------------
  文中这个公式，26*(h[i-1]-26^(m-1)*h[i-1])可以化简为26*h[i-1]*(1-26^(m-1))，所以这里是不是应该改为26*(h[i-1]-26^(m-1)*s[i-1])，用s[i-1]代表当前位置的字符串的值，例如图中d的值是3，同样的公式后面加 h[i+m-1]是不是也是s[i+m-1]呢

  作者回复: 写错了 感谢指正 已经改了

  2018-12-05

   1

   10
• 

  coulson

  老师，前天面试被问到一个问题，关于地图算法的，比如线路推荐。请问地图算法会讲到么

  作者回复: 在高级篇那部分会涉及一点

  2018-12-05

   1

   7
• 

  朱月俊

  以前刷题的时候，遇到过rk算法，当时是没太考虑hash冲突，一个字母对应一个数字，子串的hash值就是子串中的字母对应的数字想加。
  今天大佬将之抽象提炼出来，还专门提到冲突解决方法，不可谓不妙！

  2018-12-05

  

   7
• 

  yaya

  二维矩阵只要如果以i'j为左上角，即可定义一个i.j i+1.j i. j+1 i+1.j+1的子串，其本质是和字符串相同的，即可以由rf又可以由bf解

  2018-12-05

  

   6
• 

  蒋礼锐

  思考题:
  可以先查找第一行的字符串，假设长度为m，用bf或者rk都可以，假设是n*n的数组，
  bf的复杂度是(n-m)*n
  rk的复杂度为n
  
  如果有匹配，则依次匹配第2到m行字符串。每次的复杂度与第一次的相同
  
  最坏时间复杂度为
  bf:(m-n)^2*n^2
  rk:n^2
  
  但是如果第一行不匹配的话是不会进行第二行的匹配的，平均复杂度会小很多。

  2018-12-05

  

   5
• 

  煦暖

  “h[i] = 26*(h[i-1]-26^(m-1)*h[i-1]) + h[i+m-1];其中, h[i]、h[i-1] 分别对应 s[i] 和 s[i-1] 两个子串的哈希值。”老师你好，26^(m-1)*h[i-1]中的h[i-1]和h[i+m-1]应该是一个字符的哈希值而不应该是子串的哈希值吧？？PS：用您的例子套用公式：h0 = 3*26*26+1*26+2 = 2056；h1=26*(h0-26*26*h0)+(4*26*26+3*26+4) = -36080014 和期望的哈希值1*26*26+2*26+4=732不符。
  
  

  2018-12-05

   1

   4
• 

  晓龙

  RK算法有两个可以改进的点，一个可以避免hash冲突，另一个可以减少hash计算次数。
  
  改进一：先计算模式串的hash值，记录下来，然后计算每一个子串的hash，计算一次，就对比一次，如果hash值匹配，在全量对比字符串。这样做可以不用关心hash冲突问题。
  
  改进二：计算子串hash值的时候只要计算到n-（n-m）处即可，剩下的子串长度小于模式串，不用计算。
  

  2019-03-01

  

   3
• 

  Rephontil

  h[i] = 26*(h[i-1]-26^(m-1)*(s[i-1]-'a')) + (s[i+m-1]-'a');
  其中, h[i]、h[i-1] 分别对应 s[i] 和 s[i-1] 两个子串的哈希值
    好吧，这一段代码我对照上下文看了10遍，看懂了。我承认我很蠢

  作者回复: 抱歉 没写清楚

  2019-01-09

  

   3
• 

  Rephontil

  老师您应该把公式的推理过程简单地说一下，这公式对您来说非常简单，但是对于我这种基础差的人，完全是懵逼的状态。看着大家讨论，却无法深入下去。/(ㄒoㄒ)/~~

  作者回复: 我补一下

  2019-01-09

  

   3
• 

  星君

  好几期没看了，感觉跟不上了

  作者回复: 不着急 慢慢来 没必要一直紧跟着

  2018-12-12

  

   3
• 

  hunterlodge

  RK算法和布隆过滤器的思想是一致的

  2018-12-07

  

   3
• 

  王婵

  思考题二维数组用RK算法计算哈希值要复杂一些，i-1 j-1不越界的情况下，如果模式串的行数大于列数可以通过h[i-1,j]计算h[i,j]，如果列数大于行数可以通过h[i,j-1]计算h[i,j] 还有更好的方法计算哈希值吗？
  另外正文里的计算哈希值的公式貌似写错了，应该是
  h[i] = 26*(h[i-1]-26^(m-1)*(s[i-1]-‘a’)) + (s[i+m-1]-‘a’);

  2018-12-05

  

   3
• 

  qinggeouye

  RK 算法，计算相邻两个子串哈希值的规律，比如，相邻两个子串分别为 "dbc" 和 "bce"，那么 s[i-1] = 'd'，s[i]='b' ，与 'a' 相减意思是，它们的 ASCII 码值的差值正好表示字母的数值；
  评论中有同学不明白老师给的哈希值 h[i] 和 h[i-1] 之间的关系，我想应该是 s[i] 和 s[i-1] 代表什么这点没明白。

  2018-12-31

  

   2
• 

  大刚

  老师，下面的不懂，能不能在详细讲解下
  h[i] = 26*(h[i-1]-26^(m-1)*(s[i-1]-'a')) + (s[i+m-1]-'a');

  2018-12-20

  

   2
• 

  漫漫越

  停看了好多天，最后还是决定继续跟随老师的脚步，为自己加油~

  作者回复: 停一停 歇歇挺好的 也没必要跟的很紧 搞的自己很窘迫

  2018-12-18

  

   2