大きな文字列のRabin Karpアルゴリズム

Question

部分文字列検索のためのRabin-Karpアルゴリズムの簡単なステップバイステップ実装を書いたところ、ハッシュ値が係数より大きくなるまでうまくいくように見えますここで

がコードです、それは非常に簡単です：

typedef long long ll; 

#define B 257 
//base 
#define M 2147483647 
//modulus 

//modulus for positive and negative values 
ll mod(ll a){ 
    return (a % M + M) % M; 
} 

//fast way to calculate modular power 
ll power(ll n, ll e){ 
    ll r = 1; 
    for(; e > 0; e >>= 1, n = (n*n) % M) 
     if(e&1) r = (r * n) % M; 
    return r; 
} 

//function to calculate de initial hash 
//H(s) = s[0] * B^0 + s[1] * B^1 + ... 
ll H(char sub[], int s){ 
    ll h = 0; 
    for(ll i = 0; i < s; i++) 
     h = mod(h + mod(power(B, i) * sub[i])); 
    return h; 
} 

//brute force comparing when hashes match 
bool check(char text[], char sub[], int ini, int s){ 
    int i = 0; 
    while(text[ini + i] == sub[i] && i < s) i++; 
    return i == s; 
} 

//all together here 
void RabinKarp(char text[], char sub[]){ 
    int t = strlen(text), s = strlen(sub); 
    ll hs = H(sub, s), ht = H(text, s); 
    int lim = t - s; 

    for(int i = 0; i <= lim; i++){ 
     if(ht == hs) 
      if(check(text, sub, i, s)) 
       printf("MATCH AT %d\n", i);   

     ht -= text[i];  
     ht /= B;    
     ht = mod(ht + power(B, s - 1) * text[i + s]); 

     //we had text[i] * B^0 + text[i+1] * B^1 + ... + text[i + len - 1] * B^(len-1) 

     //then text[i+1] * B^1 + text[i+2] * B^2 + ... + text[i + len - 1] * B^(len-1) 
     //then text[i+1] * B^0 + text[i+2] * B^1 + ... + text[i + len - 1] * B^(len-2) 
     //finally we add a new last term text[i + len] * B^(len-1) 

     //so we moved the hash to the next position 
    } 
} 



int main(){ 
    char text[] = "uvauvauvaaauva"; 
    char sub[] = "uva"; 
    char sub2[] = "uvauva"; 
    RabinKarp(text, sub); 
    printf("----------------------------\n"); 
    RabinKarp(text, sub2); 
} 

問題は、私はモジュラスを取る後、私はそれにいくつかの大きな要因を追加するときに、ハッシュは、その後、小さな数になるとできることです、必要な場合でもハッシュが一致しないことがあります。例えば

：ABC

私はABCとXABのハッシュを取るXABC

の内側に、それらの両方が、弾性率よりも大きいですので、彼らは、剰余演算の後に小さなもらうとします。

次に、 'x'を削除して 'c'因子を追加すると、合計はモジュラスよりも小さくてもまだ大きいので、一致しません。

どうすればこの問題を解決できますか？

Answer 1

ht/= B; はそうではありません。まず第一に、あなたが算術mod Mを実行していることと、除算のモジュール等価が標準のものと同じではないためです。第二に、あなたはxとx + Mについて同じ答えを期待しなければならないので、これは当てはまりません。

テキストを持っている[I] * B^0 +テキスト[I + 1] * B^1 + ... +テキストは[私はLEN + - 1] * B ^（LEN-1）

テキスト[i] * B（len-1）+テキスト[i + 1] * B ^（len-2）+ ...テキスト+ i + len-1] * B^0

あなたはテキスト[I] * B ^（LEN-1）を差し引くと、彼らはあなたが意図する方法を作業していることを確認するために機能上のBで代わりに