Сопоставление строк Рабина-Карпа не соответствует

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

Прототип

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 в качестве основания и 13 в качестве простого числа. Я ожидаю, что будет одно фактическое совпадение и одно ложное совпадение, но я никогда не получаю оператор вывода из соответствующей части функции. Что я делаю неправильно?

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


c++ algorithm string-matching rabin-karp
person Madison S    schedule 04.12.2010    source источник

Ответы (2)


arrow_upward
8
arrow_downward

Большой проблемой в кодировании Рабина Карпа является оператор по модулю. Когда два числа 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 в основном цикле необходимо добавить аналогичную проверку.

person paperhorse    schedule 04.12.2010

arrow_upward
5
arrow_downward

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

person jonderry    schedule 04.12.2010
comment
Спасибо! Это помогло решить проблему, с которой я столкнулся, когда h был неправильным. Я не знал, что оператор ^ не был определен как возведение в степень. Все еще не получаю вывод :( - person Madison S; 04.12.2010
comment
Я бы проверил, что небольшие его части ведут себя так, как ожидалось, вместо того, чтобы пытаться заставить все работать сразу. Это поможет вам найти ваши ошибки один за другим. - person jonderry; 04.12.2010
comment
Проходя через GDB, я обнаружил виновника: пересчет t во втором цикле for приводит к отрицательным числам. Все остальное работает как надо, насколько я могу судить. - person Madison S; 04.12.2010