#c #hash #rabin-karp
#c #хэш #rabin-karp
Вопрос:
Приносим извинения за этот вероятный повторяющийся вопрос.
Я пытаюсь использовать скользящий хэш с Karp Rabin.Я просмотрел разные реализации скользящего хэша, и мне интересно, где я ошибаюсь. Хотя текст имеет шаблон, совпадение с использованием хэша, похоже, вообще не происходит. Прикрепление (части) кода для вычисления хэша и поиска.
long hash(char* key, int len) {
int j = 0;
unsigned long long h = 0;
for (j = 0; j < len; j ) {
h = h * PRIME_BASE key[j];
h %= PRIME_MOD;
}
return h;
}
int search(char* pattern, char *txt, int textLength, int patternLength) {
int i, val = 0;
long long txtHash=0;
long power = 1;
for (i = 0; i < patternLength; i )
power = (power * PRIME_BASE) % PRIME_MOD;
i=0;
printf(" the value of power is %ld ",power);
for (i = 0; i < textLength; i ) {
txtHash = txtHash * PRIME_BASE txt[i];
txtHash %= PRIME_MOD;
if (i >= patternLength)
{
txtHash -= power * txt[i - patternLength] % PRIME_MOD;
if (txtHash < 0){
//negative can be made positive with mod
txtHash = PRIME_MOD;
}
}
int offset=0;
if(i>=patternLength){
offset=i-patternLength 1;
}
else{
offset=0;
}
if (patHash == txtHash) {
if (check(pattern, txt, offset, patternLength)) {
val ;
}
}
}
if (val > 0) {
return val;
}
// no match
return 0;
}
bool check(char* pattern, char* txt, int k, int M) {
int j = 0;
for (j = 0; j < M; j ) {
if (pattern[j] != txt[k j]) {
return false;
}
}
return true;
}
У меня была проблема с переполнением буфера, с которой я имел дело, но шаблон и текстовый хэш, похоже, не совпадают для текстовой строки последовательности белка (с 1000 символами) и шаблоном из 17 символов
Есть идеи, в чем я мог ошибиться?
Спасибо, Bhavya
Комментарии:
1. вместо скользящего хэша я использовал вычисленный хэш текста путем повторного вызова хэш-функции, и это, похоже, работает, но, конечно, производительность так же плоха, как и алгоритм грубой силы
Ответ №1:
Я потратил еще некоторое время на эту проблему и обнаружил, что, поскольку я инициализировал значение long long txtHash некоторым значением по умолчанию, я столкнулся с ситуацией, когда хэши не совпадали. обновление приведенного выше кода с исправлением