algorithm - 用于字符串匹配的 Rabin-Karp 方法

Question

使用 Rabin-Karp 方法进行字符串匹配，该方法使用了多少个字符-字符匹配？在哪里：

source  = abcabcabcacd
pattern = bcac

Answer 1

让我们从算法本身开始。Rabin-Karp 方法如何工作。我将使用C#代码进行说明。有

  string target = "bcac";
  string source = "abcabcabcacd";

我们计算哈希target：

  int targetHash = RabinHash(target);

然后有效地计算所有长度子串target（这里是长度子串4）的散列： "abca", "bcab", ... "cacd"。如果targetHash 等于子字符串的哈希值，我们会比较这个子字符串和 target相应的字母。例如：

如果targetHash = 888和对于子字符串，我们有，比如说，

  abca : 555 
  bcab : 345 
  cabc : 888 <- check this (failure due to hash collision)
  abca : 555 
  bcab : 345 
  cabc : 888 <- check this (failure due to hash collision) 
  abca : 555 
  bcac : 888 <- check this (success)
  cacd : 900  
 

在这里，我们有 3 集字符-字符匹配。现在我们准备回答您的问题：字符匹配的数量取决于散列函数。

最坏的情况：我们只有哈希冲突：

  int RabinHash(string value) => 1;

所有9个子字符串都应进行字符检查。

最好的情况：我们没有哈希冲突；比如说，我们可以实现一个典型的 Rabin 哈希函数

  int RabinHash(string value) => value.Aggregate(0, (s, a) => s * 26 + a - 'a');

我们应该检查唯一的1 个实际匹配：

  string target = "bcac";
  string source = "abcabcabcacd";

  // int RabinHash(string value) => 1;
  int RabinHash(string value) => value.Aggregate(0, (s, a) => s * 26 + a - 'a');

  int targetHash = RabinHash(target);

  var report = Enumerable
    .Range(0, source.Length - target.Length + 1)
    .Select(i => source.Substring(i, target.Length))
    .Select(chunk => new { 
      chunk,
      hash = RabinHash(chunk)
    })
    .Select(item => $"{item.chunk} : {item.hash,5} {(item.hash == targetHash ? "<- check it" : "")}");

  Console.Write(report);

结果：

  abca :   728 
  bcab : 18929 
  cabc : 35180 
  abca :   728 
  bcab : 18929 
  cabc : 35180 
  abca :   728 
  bcac : 18930 <- check it
  cacd : 35207

最终答案：根据散列函数，我们必须1多次检查9。