Rabin Karp字符串匹配算法
我在网站的论坛上看过这个Rabin Karp字符串匹配算法，我有兴趣尝试实现它，但我想知道如果有人能告诉我为什么变量ulong Q和ulong D分别是100007和256：S ？ 这些价值观带有什么意义？
static void Main(string[] args) { string A = "String that contains a pattern."; string B = "pattern"; ulong siga = 0; ulong sigb = 0; ulong Q = 100007; ulong D = 256; for (int i = 0; i >{0}<<{1}", A.Substring(0, B.Length), A.Substring(B.Length))); return; } ulong pow = 1; for (int k = 1; k <= B.Length - 1; k++) pow = (pow * D) % Q; for (int j = 1; j >{1}<<{2}", A.Substring(0, j), A.Substring(j, B.Length), A.Substring(j + B.Length))); return; } } } Console.WriteLine("Not copied!"); } 关于神奇的数字保罗的回答非常明确。
就代码而言，Rabin Karp的主要思想是在字符串的滑动部分和模式之间执行哈希比较。
每次在整个子串上都不能计算散列，否则计算复杂度将是二次O(n^2)而不是线性O(n) 。
因此，应用滚动散列函数，例如在每次迭代时，仅需要一个字符来更新子串的散列值。
那么，让我们评论你的代码：
for (int i = 0; i < B.Length; i++) { siga = (siga * D + (ulong)A[i]) % Q; sigb = (sigb * D + (ulong)B[i]) % Q; } if (siga == sigb) { Console.WriteLine(string.Format(">>{0}<<{1}", A.Substring(0, B.Length), A.Substring(B.Length))); return; }
^这个部分计算模式B （ sigb ）的散列，以及相同长度B的A的初始子串的散列码。 实际上它并不完全正确，因为哈希可以碰撞¹所以，有必要修改if语句： if (siga == sigb && A.Substring(0, B.Length) == B) 。
ulong pow = 1; for (int k = 1; k <= B.Length - 1; k++) pow = (pow * D) % Q;
^这是计算执行滚动哈希所必需的pow 。
for (int j = 1; j <= A.Length - B.Length; j++) { siga = (siga + Q - pow * (ulong)A[j - 1] % Q) % Q; siga = (siga * D + (ulong)A[j + B.Length - 1]) % Q; if (siga == sigb) { if (A.Substring(j, B.Length) == B) { Console.WriteLine(string.Format("{0}>>{1}<<{2}", A.Substring(0, j), A.Substring(j, B.Length), A.Substring(j + B.Length))); return; } } }
^最后，扫描剩余的字符串（即从第二个字符到结束），更新A子串的哈希值，并与B的哈希值（在开头计算）进行比较。
如果两个哈希值相等，则比较子字符串和模式¹，如果它们实际上相等，则返回一个消息。
¹ 哈希值可能会发生碰撞 ; 因此，如果两个字符串具有不同的哈希值，它们肯定是不同的，但如果两个哈希值相等，它们可以相等或不相同。
该算法使用散列进行快速字符串比较。 Q和D是编码器可能通过一些试验和错误得到的神奇数字，并且为这个特定算法提供了良好的散列值分布 。
您可以看到用于散列许多地方的这些类型的幻数。 下面的示例是.NET 2.0字符串类型的GetHashCode函数的反编译定义：
[ReliabilityContract(Consistency.WillNotCorruptState, Cer.MayFail)] public override unsafe int GetHashCode() { char* chrPointer = null; int num1; int num2; fixed (string str = (string)this) { num1 = 352654597; num2 = num1; int* numPointer = chrPointer; for (int i = this.Length; i > 0; i = i - 4) { num1 = (num1 << 5) + num1 + (num1 >> 27) ^ numPointer; if (i <= 2) { break; } num2 = (num2 << 5) + num2 + (num2 >> 27) ^ numPointer + (void*)4; numPointer = numPointer + (void*)8; } } return num1 + num2 * 1566083941; }
以下是R＃为样本类型生成的GetHashcode覆盖函数的另一个示例：
public override int GetHashCode() { unchecked { int result = (SomeStrId != null ? SomeStrId.GetHashCode() : 0); result = (result*397) ^ (Desc != null ? Desc.GetHashCode() : 0); result = (result*397) ^ (AnotherId != null ? AnotherId.GetHashCode() : 0); return result; } }