Rabin-Karp
参考:
https://www.cnblogs.com/tanxing/p/6049179.html
首先计算模式字符串的散列函数, 如果找到一个和模式字符串散列值相同的子字符串,...基本思想
长度为M的字符串对应着一个R进制的M位数, 为了用一张大小为Q的散列表来保存这种类型的键, 需要一个能够将R进制的M位数转化为一个0到Q-1之间的int值散列函数, 这里可以用除留取余法....举个例子, 需要在文本 3 1 4 1 5 9 2 6 5 3 5 8 9 7 9 3 查找模式 2 6 5 3 5, 这里R=10, 取Q=997, 则散列值为
2 6 5 3 6 % 997 = 613...算法实现:
构造函数为模式字符串计算了散列值patHash并在变量中保存了R^(M-1) mod Q的值, hashSearch()计算了文本前M个字母的散列值并和模式字符串的散列值比较, 如果没有匹配..., 文本指针继续下移一位, 计算新的散列值再次比较,知道成功或结束.