Поиск по шаблону с использованием Rabin Karp

Question

Я работаю над алгоритмом Рабина Карпа, используя формулу повторения. Ниже приведен код. В коде я проверяю значение хеша, рассчитанное обычным способом и по формуле повторения. Оба значения не совпадают. Я потратил достаточно времени почти на 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

Проблема в том, что я вычисляю mod по целому числу без знака std64, поэтому mod становится положительным, что зависит от реализации

Ссылка: C++03 пункт 5.6 пункт 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;