用于字符串匹配的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子字符串进行字符-字符检查。

最好的情况：我们没有散列冲突；比如说，我们可以实现一个典型的拉宾散列函数为

  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的时间。