滾動哈希的實現無助於與Rabin Karp進行字符串匹配

對於這個可能的重複問題抱歉。滾動哈希的實現無助於與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個字符圖案任何問題想法可能會出錯？

感謝，巴維亞

來源

2011-10-19 bhavs

而不是一個滾動散列我使用通過重複調用散列函數計算文本的散列，這似乎是工作，但當然性能是壞作爲蠻力算法 – bhavs

我花了在這個問題上的一些更多的時間和發現，因爲我已經初始化長長txtHash的價值，一些默認值我正面臨着其中的哈希值是不匹配的情況。更新上面的代碼與修復

來源

2011-10-20 07:59:34 bhavs

滾動哈希的實現無助於與Rabin Karp進行字符串匹配

回答

相關問題