Rabin-Karp字符串匹配算法

Question

我在网站的论坛上看到了这个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 < 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!");
}

- c grum

---

我不熟悉这个算法。我只做到了第一个包含错误的 for () {} 循环。如果 B.Length > A.Length 会怎样？会出现 IndexOutOfRangeException。 - Tergiver

阅读完维基百科文章（http://en.wikipedia.org/wiki/Rabin%E2%80%93Karp_algorithm）后，我可以看出Q是用于哈希子字符串的“大质数”。D似乎是一个缩放因子，它将每个新字符位置视为256的倍数，但这似乎假定没有字符值>= 256。不过在这方面我并不是专家。 - Tergiver

D 为 256 实际上是将其左移 8 位，以为下一个字符腾出空间（尽管这是一种 ASCII 中心的观点）。 - payo

Answer 1

关于魔术数字，Paul的回答已经很清楚了。就代码而言，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的哈希值（在开头计算）进行比较。

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

---

¹ 哈希值可能会发生碰撞；因此，如果两个字符串的哈希值不同，它们肯定是不同的，但如果两个哈希值相等，则它们可能相等也可能不相等。

- digEmAll

---

非常感谢您通过注释代码来帮助我。非常感激！ - c grum

Answer 2

该算法使用哈希算法进行快速字符串比较。Q和D是程序员可能通过一些试错得出的魔数，并为该特定算法提供了良好的哈希值distribution。

你可以在许多地方看到这种用于哈希的魔数。下面的示例是.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;
        }
    }

- Paul Sasik