Строковое сопоставление Rabin-Karp не соответствует

Question

Я работал над функцией сопоставления строки Rabin-Karp в C ++, и я не получаю никаких результатов из этого. У меня есть ощущение, что я правильно не вычисляю некоторые значения правильно, но я не знаю, какие из них.

Прототип

void rabinKarp(string sequence, string pattern, int d, int q);

Реализация функций

void rabinKarp(string sequence, string pattern, int d, int q)
{
    //d is the |∑|
    //q is the prime number to use to lessen spurious hits
    int n = sequence.length(); //Length of the sequence
    int m = pattern.length(); //Length of the pattern
    double temp = static_cast<double> (m - 1.0);
    double temp2 = pow(static_cast<double> (d), temp); //Exponentiate d
    int h = (static_cast<int>(temp2)) % q; //High Order Position of an m-digit window
    int p = 0; //Pattern decimal value
    int t = 0; //Substring decimal value
    for (int i = 1; i < m; i++) { //Preprocessing
        p = (d*p + (static_cast<int>(pattern[i]) - 48)) % q;
        t = (d*t + (static_cast<int>(sequence[i])-48)) % q;
    }
    for (int s = 0; s < (n-m); s++) { //Matching(Iterate through all possible shifts)
        if (p == t) {
            for (int j = 0; j < m; j++) {
                if (pattern[j] == sequence[s+j]) {
                    cout << "Pattern occurs with shift: " << s << endl;
                }
            }
        }
        if (s < (n-m)) {
            t = (d*(t - ((static_cast<int>(sequence[s+1]) - 48)*h)) + (static_cast<int>(sequence[s + m + 1]) - 48)) % q;
        }
    }
    return;
}

В моей функции позвоните мне через 2359023141526739921, что и последовательность, 31415 в качестве шаблона, 10 в качестве Radix и 13, как Prime. Я ожидаю, что будет один фактический матч и один ложный хит, но я никогда не получаю выходной оператор из соответствующей части функции. Что я делаю неправильно?

Спасибо заранее, Мэдисон

Answer 1

Большая Гоща в кодировании Rabin Karp является Оператор модуля. Отказ Когда два числа X и Y являются конгруэнтными модулями q, то (x% q) должно быть равно (y% q), но на компилятору C ++, вы используете, они будут равны только, если X и Y являются положительными, либо как отрицательными. Если X положительный, а y отрицательный, то (x% Q) будет положительным, и (y% q) будет отрицательным. На самом деле (x% Q) -q == (y% q) в этом случае.

Работа вокруг состоит в том, чтобы проверить наличие отрицательных значений после каждого модуля, и если есть какие-либо добавлять q к переменной, поэтому ваш петлю предварительной обработки становится:

    p = (d*p + pattern[i]) % q;
    if ( p < 0 ) p += q;
    t = (d*t + sequence[i]) % q;
    if ( t < 0 ) t += q;

T в основной петли должен быть добавлен аналогичный чек.

Answer 2

Если вы не перенесли ^, это вычисляет XOR, а не экспоненцию. Кроме того, вы должны быть осторожны о переполнении максимального значения int Прежде чем вы выполнять %.