gpt4 book ai didi

c# - Rabin Karp字符串匹配算法

转载 作者:可可西里 更新时间:2023-11-01 07:56:59 27 4
gpt4 key购买 nike

我在网站的论坛上看到过这个 Rabin Karp 字符串匹配算法,我有兴趣尝试实现它,但我想知道是否有人能告诉我为什么变量 ulong Q 和 ulong D 是 100007 和 256分别:S?这些值(value)观有什么意义?

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!");
}

最佳答案

关于魔数(Magic Number),Paul 的回答非常明确。

就代码而言,Rabin Karp 的主要想法是在字符串的滑动部分和模式之间执行哈希比较。

不能每次都对整个子串计算散列,否则计算复杂度将是二次O(n^2)而不是线性O(n)

因此,一个 rolling hash应用函数,例如在每次迭代中只需要一个字符来更新子字符串的哈希值。

那么,让我们评论你的代码:

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),以及A<的初始子串的散列码B 的长度相同。实际上它并不完全正确,因为散列可以碰撞¹,所以有必要修改 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 的哈希值(在开头计算)进行比较。

如果两个哈希值相等,则比较子字符串和模式¹,如果它们实际上相等,则返回一条消息。


¹ Hash values can collide ;因此,如果两个字符串具有不同的散列值,则它们肯定不同,但如果两个散列值相等,则它们可以相等或不相等。

关于c# - Rabin Karp字符串匹配算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/10338379/

27 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com