Rabin Karp String Matching Algorithmus
Ich habe diesen Rabin Karp String Matching-Algorithmus in den Foren auf der Website gesehen und bin daran interessiert, ihn zu implementieren, habe mich aber gefragt, ob mir jemand sagen könnte, warum die Variablen ulong Q und ulong D jeweils 100007 und 256 sind: S ? Welche Bedeutung haben diese Werte?
<code>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 < 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; } ulong pow = 1; for (int k = 1; k <= B.Length - 1; k++) pow = (pow * D) % Q; 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; } } } Console.WriteLine("Not copied!"); } </code>