Rabin-Karp String Matching не подходит

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

Спасибо заранее, Madison

Answer 1

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

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

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

т в главном цикле необходимо иметь аналогичная проверка добавлена.

Answer 2

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