Строка соответствует для некоторых случаев, а не для других, использующих алгоритм Рабина Карпа? - PullRequest
Новая
       57

Строка соответствует для некоторых случаев, а не для других, использующих алгоритм Рабина Карпа?

0 голосов
/ 29 октября 2018 
// n -> length of the text
// m -> length of the pattern    
void rabin_karp_check(int n, int m){
        int h_p = hash_value(pattern, m, 0);       
        int h_t = hash_value(text, m, 0); 
        int x = 0;
        int i = 0,k;
        while(i < n - m + 1){
            if(x > 0){
                h_t = rolling_hash(h_t, m, i);  
                }
            x++;
            int j = i;
            if(h_t == h_p){   
                int match_count = 0;
                k = 0;
                while( match_count < m){        
                    if(pattern[k] == text[j]){
                        match_count++;  k++; j++;
                    }
                    else
                        break;
                }
                if(match_count == m)
                    cout<<"found at "<<i<<"\n";
            }
            i++;
        }
    }

функция для вычисления хеш-значения шаблона и начального слайда размером m текста используя hash_formula 

//(256^m-1 * p[0] + 256^m-2 * p[1] + 256^m-3 * p[2] + .... + 256^0 * p[m-1]) % q

int hash_value(string &p, int &m, int i){

        int q = 101,k = 0;    
        long long int l = 0;
        for(int j = i;j < i + m ; j++){
            l = l + pow(256, m - 1 - k) * p[j];
            k++;
        }
        return l % q;               
    }

Функция для вычисления следующего значения хеша с использованием предыдущего вычисленного 

int rolling_hash(int h_t, int m, int i){   
        int x = (   ( (h_t - ((long int)pow(256, m - 1) * text[i-1])) * 256)  +  text[i + m - 1] ) % 101;
            return (x < 0) ? x + 101 : x;
    }

Выход № 1: 

enter the text: platform for showcasing
enter the pattern: for
found at 4
found at 9

Выход № 2: не обнаружено 

enter the text: karp rabin
enter the pattern: rabin

Выход № 3: обнаружено 

enter the text: best practices in
enter the pattern: ic
found at 10

Выход № 4: не обнаружено 

enter the text: would you like to hear me tell a joke
enter the pattern: hear

Я не могу понять, почему это происходит. Я думаю, что в некоторых случаях значение хеш-функции, вычисляемое путем свертывания хеш-функции из ранее сохраненного значения хеш-функции, не равно фактическому значению хеш-функции для этого размера (м) текста. где я не так делаю?

Заранее спасибо

...