Реализация скользящего хэша не помогает в согласовании строк с Рабином Карпом - PullRequest
Новая
       36

Реализация скользящего хэша не помогает в согласовании строк с Рабином Карпом

3 голосов
/ 19 октября 2011

Извиняюсь за этот вероятный повторяющийся вопрос.

Я пытаюсь использовать катящийся хеш с Карпом Рабином. Я смотрел различные реализации катящегося хэша, и мне интересно, где я ошибаюсь.Хотя в тексте есть шаблон, совпадение с использованием хэша, похоже, вообще не происходит.Прикрепление (часть) кода для вычисления хеша и поиска.

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 символовЕсть идеи, где я могу ошибаться?

Спасибо, Бхавья

1 Ответ

0 голосов
/ 20 октября 2011

Я потратил еще немного времени на эту проблему и обнаружил, что, поскольку я инициализировал значение long long txtHash некоторым значением по умолчанию, я столкнулся с ситуацией, когда хэши не совпадали.обновив код выше с исправлением

...