求帮忙看看哪里有问题！# JobHunting - 待字闺中
J*3
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;
}
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
%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;
}