c++ - 使用 Rabin Karp 进行模式搜索

Question

我正在研究使用递归公式的 Rabin Karp 算法。以下是代码。在代码中，我正在检查以正常方式和递归公式计算的哈希值。两个值都不匹配。我花了将近 3 个小时的时间进行调试，不确定是什么问题。请求您帮助查找错误。

#include <iostream>
#include <fstream>
#include <streambuf>
#include <cstdint>
#include <string>
#include <vector>

const std::uint64_t uiLargePrime    = 1000000007;
const unsigned int  uiXValue        = 263; 
const unsigned int  uiHashTableSize = 79;



struct sCalcHash {

    std::uint64_t operator() (const std::string& strText) {
        // user horners method.
        unsigned int uiStrLength =  strText.length();
        std::uint64_t uiResult = 0;

        // calculate hash value
        for(int uiIdx = (uiStrLength - 1); uiIdx >= 0; uiIdx--) {
            uiResult = (((uiResult * uiXValue) % uiLargePrime) + strText[uiIdx]) % uiLargePrime ;
        }
        // return uiResult % uiHashTableSize;
        return uiResult;
    }
};

// calculate x ^ uiPatternLength % uiLargePrime.
unsigned int expValueOfX(unsigned int uiXVal, unsigned int uiPower) {
    // get X value in range of prime;
    uiXVal = uiXVal % uiLargePrime; 
    unsigned int uiResult = 1;
    while (uiPower > 0 ) {

        // check if power is odd
        if (uiPower & 1) {
            uiResult = ((uiResult % uiLargePrime) * (uiXVal % uiLargePrime) ) % uiLargePrime;
        }

        // now uiPower is even
        uiPower = uiPower >> 1;
        uiXVal = ((uiXVal % uiLargePrime) * (uiXVal % uiLargePrime)) % uiLargePrime;
    }
    return uiResult;
}

// Rabin Karp Algorithm

void RabinKarpAlgo(std::string& Text, std::string& pattern) {

    std::vector<unsigned int> vecPostions;

    //calculate hash value of pattern.
    sCalcHash hash;
    std::uint64_t hashValPattern = hash(pattern);
    std::cout << "Hash Value of pattern: " <<  hashValPattern  << std::endl;

    unsigned int uiPatternLength = pattern.length();
    // calculate x ^ uiPatternLength % uiLargePrime.
    unsigned int uiXExpVal = expValueOfX(uiXValue, uiPatternLength);
    //std::cout << "Exponential value  " <<  uiXExpVal  << std::endl;
    // calculate hash value 
    unsigned int uiStrLength = Text.length();
    // calculate hash value of last part of string of pattern length.
    unsigned int uiLastIdx = uiStrLength - uiPatternLength;
    std::uint64_t hashValLastIdx = hash(Text.substr(uiLastIdx));
    std::cout << "Hash Value of last indx of text: " <<  hashValLastIdx  << std::endl;

    // if hash value is same then compare string
    if (hashValLastIdx == hashValPattern) {
        if(pattern == Text.substr(uiLastIdx)) {
            std::cout << "Pushing index: " << uiLastIdx << std::endl;
            vecPostions.push_back(uiLastIdx);
        }
    }
    for(int uiIdx = uiLastIdx - 1; uiIdx >= 0; uiIdx--) {
        // calculate hash value of string
        std::int64_t iHashValRecur = ( (Text[uiIdx] % uiLargePrime) + 
                                       ((hashValLastIdx % uiLargePrime) * (uiXValue % uiLargePrime)) % uiLargePrime - 
                                       ((Text[uiIdx + uiPatternLength] % uiLargePrime) * (uiXExpVal % uiLargePrime) ) % uiLargePrime
                                     ) % uiLargePrime;
        unsigned int iHashVal = hash(Text.substr(uiIdx, uiPatternLength));

        std::cout << "Hash Value of with recurr " << uiIdx << " is " << iHashValRecur <<  " and with hash func: " << iHashVal << std::endl;



        if(iHashValRecur == hashValPattern) {
            // compare string
            if(pattern == Text.substr(uiIdx, uiPatternLength) ) {
                std::cout << "Pushing index: " << uiIdx << std::endl;
                vecPostions.push_back(uiIdx);
            }
        }
        hashValLastIdx = iHashValRecur;
    }

    // print vectors
    for( int uiIdx = vecPostions.size() - 1; uiIdx >= 0; uiIdx--) {
        std::cout << vecPostions[uiIdx] << " ";
    }
    std::cout << std::endl;

    return ;


}




int main() {

    std::ifstream inputFile("rabinkarp.in");
    std::streambuf *pCinbuf = std::cin.rdbuf();
    std::cin.set_rdbuf(inputFile.rdbuf());

    std::string strText;
    std::string strPattern;

    std::cin >> strPattern;
    std::cin >> strText;


    std::cout << "Text: " << strText << std::endl;
    std::cout << "Pattern: " << strPattern << std::endl;

    RabinKarpAlgo(strText, strPattern); 


    return 0;
}

Text: baaaaaaa
Pattern: aaaaa
Hash Value of pattern: 853306522
Hash Value of last indx of text: 853306522
Pushing index: 3
Hash Value of with recurr 2 is 435650523 and with hash func: 853306522
Hash Value of with recurr 1 is 9779548 and with hash func: 853306522
Hash Value of with recurr 0 is 5713908 and with hash func: 853306523
3
Press any key to continue . . .

预期答案是:1 2 3

Answer 1

问题是我通过无符号 std64 整数计算 mod，因此 mod 变为正数，这取决于实现

引用:C++03 paragraph 5.6 clause 4:

二进制/运算符产生商，二进制 % 运算符产生第一个表达式除以第二个表达式的余数。如果/或 % 的第二个操作数为零，则行为未定义；否则 (a/b)*b + a%b 等于 a。如果两个操作数都是非负的，则余数是非负的；如果不是，余数的符号是​​实现定义的。

所以为了避免这个问题，我在下面尝试将大素数数据类型更改为 int64_t，它在下面工作并完成了

std::int64_t iHashValRecur =  ( (Text[uiIdx] % uiLargePrime) + 
                                     ((uiXValue  % uiLargePrime * hashValLastIdx  % uiLargePrime)  % uiLargePrime) -
                                     ((Text[uiIdx + uiPatternLength]  % uiLargePrime * (uiXExpVal  % uiLargePrime))  % uiLargePrime)
                                     );

        std::int64_t iHashVal = hash(Text.substr(uiIdx, uiPatternLength));
        iHashValRecur = iHashValRecur  % uiLargePrime;
        while (iHashValRecur < 0) { 
            iHashValRecur += uiLargePrime; 
        } 
        iHashValRecur = iHashValRecur % uiLargePrime;