c# - 使用 C# 实现 Rabin-Karp 算法以在 LeetCode 28 "implement strStr()"中搜索字符串的问题

Question

我实现了这个算法来解决 Leetcode 的 #28 问题“implemment strStr()”。
问题描述:
实现 strStr()， 返回 needle 在 haystack 中第一次出现的索引，如果 needle 不是 haystack 的一部分，则返回 -1。

我的代码是基于http://www.geeksforgeeks.org/searching-for-patterns-set-3-rabin-karp-algorithm/实现的的教程。

我发现使用不同的质数来缩小哈希值时，函数可能会出错。
这是我的代码:

    public class Solution {
    public int StrStr(string haystack, string needle) {
        int len = needle.Length;
        //2 special case
        if (haystack.Length < len) return -1;
        if (needle == "") return 0;

        //base prime number used for rabin-karp's hash function
        int basement = 101;
        //prime number used to scale down the hash value
        int prime = 101;
        //the factor used to multiply with the character to be removed from the hash
        int factor = (int)(Math.Pow(basement, needle.Length - 1)) % prime;

        //get ascii value of the needle and the initial window
        int needleHash = 0;
        int windowHash = 0;
        byte[] needleBytes = Encoding.ASCII.GetBytes(needle);
        byte[] windowBytes = Encoding.ASCII.GetBytes(haystack.Substring(0, len));

        //generate hash value for both
        for (int i = 0; i < needle.Length; i++)
        {
            needleHash = (needleHash * basement + needleBytes[i]) % prime;
            windowHash = (windowHash * basement + windowBytes[i]) % prime;
        }

        //loop to find match
        bool findMatch = true;
        for (int i = 0; i < haystack.Length - len + 1; i++){
            //if hash value matches, incase the hash value are not uniq, iterate through needle and window
            if(needleHash == windowHash){
                findMatch = true;
                for (int j = 0; j < len; j++)
                {
                    if (needle[j] != haystack[i + j])
                    {
                        findMatch = false;
                        break;
                    }
                }
                if (findMatch == true) return i;
            }
            //move the sliding window and find the hash value for new window
            if (i < haystack.Length - len){
                byte removeByte = Encoding.ASCII.GetBytes(haystack.Substring(i, 1))[0];
                byte addByte = Encoding.ASCII.GetBytes(haystack.Substring(i + len, 1))[0];
                //function of rolling hash
                windowHash = ((windowHash - removeByte * factor) * basement + addByte) % prime;
                //ensure the window hash to be positive
                if(windowHash < 0) windowHash += prime;
            }
        }
        return -1;
    }
}  

将“prime”设置为“101”，此代码通过了所有测试。但是，如果我将它更改为其他质数，无论大小(例如:17、31、103)，它总是在测试“68/72”时失败

haystack = "baabbaaaaaaabbaaaaabbabbababaabbabbbbab babbbbbbbababaabbbbbaaabbbbaabababababbaabbbbaaabbaaba bbbaabaabbabbaaaabababaaabbabbababbbaaabbbbabbbbbabbabbaabbbaa";
针 = "bbaaaababa";

因此我确实相信我的代码存在我无法检测到的大问题。为什么会这样？

Answer 1

您的代码有两个问题:

1. basement 应根据您用作引用的网站上的算法设置为 256。该值是输入字母表中的字符数。

2. 您对factor 的计算不正确；在计算余数之前，您要转换为 int。 Math.Pow 运算产生的 double 值大于 Int32.MaxValue。当您转换为 int before 模运算时，您将截断该值。您需要使用 double 值执行模运算，然后然后转换为 int。该行应如下所示:

   int factor = (int)((Math.Pow(basement, needle.Length - 1)) % prime);

我使用这些修改和给出的示例测试了您的代码，它适用于 17、31、101 和 103 的素数。