J****3
发帖数: 427 | 1 Strstr() using Robin-Karp alg
large case 会有6个过不了。。求大牛帮我看下哪里有问题。
const int base = 26, mod = 997;
char *strStr(char *haystack, char *needle) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int l_h = strlen(haystack);
int l_n = strlen(needle);
if(l_n > l_h) return NULL;
int h_hash = 0, n_hash = 0;
for(int i = 0; i < l_n; i++){
n_hash = (n_hash*base + needle[i])%mod;
h_hash = (h_hash*base + haystack[i])%mod;
}
int j;
for(int i = l_n; i < l_h; i++){
if(n_hash == h_hash){
for(j = 0; j < l_n; j++){
if(haystack[i+j-l_n] != needle[j]){
break;
}
}
return &haystack[i-l_n];
}
h_hash -= (haystack[i - l_n]*static_cast(pow(base, l_n-1)))
%mod;
if(h_hash < 0){
h_hash += mod;
}
h_hash = (h_hash*base + haystack[i])%mod;
}
if(n_hash == h_hash){
for(j = l_h - l_n; j < l_h; j++){
if(haystack[j] != needle[j - (l_h - l_n)]){
break;
}
}
return &haystack[l_h - l_n];
}
return NULL;
} | J****3
发帖数: 427 | 2 发现问题出在这里 static_cast(pow(base, l_n-1)) 这里应该先%mod 一次
这里发现新问题， RK里的变量h 定义就是pow(d, length(pattern) - 1) %q 可我直接
用这个公式就会有问题， 用循环求H到可以全部pass。 求解释 |
|
