gpt4 book ai didi

c++ - Rabin-Karp 算法

转载 作者:可可西里 更新时间:2023-11-01 17:13:54 25 4
gpt4 key购买 nike

我有兴趣实现 Rabin-Karp 算法来搜索 wiki 上所述的子字符串:http://en.wikipedia.org/wiki/Rabin-Karp_string_search_algorithm .不是为了功课,而是为了自己的利益。我已经实现了 Rabin-Karp 算法(如下所示)并且它有效。但是,性能真的非常差!!!我知道我的哈希函数是基本的。然而,似乎对 strstr() 的简单调用总是优于我的函数 rabin_karp()。我能理解为什么 - 散列函数比简单的逐个字符比较每个循环做的工作更多。我在这里错过了什么? Rabin-Karp 算法是否应该比调用 strstr() 更快?什么时候最好使用 Rabin-Karp 算法?因此,我的私利。我是否正确实现了算法?

size_t hash(char* str, size_t i)
{
size_t h = 0;
size_t magic_exp = 1;
// if (str != NULL)
{
while (i-- != 0)
{
magic_exp *= 101;
h += magic_exp + *str;
++str;
}
}

return h;
}

char* rabin_karp(char* s, char* find)
{
char* p = NULL;

if (s != NULL && find != NULL)
{
size_t n = strlen(s);
size_t m = strlen(find);

if (n > m)
{
size_t hfind = hash(find, m);

char* end = s + (n - m + 1);
for (char* i = s; i < end; ++i)
{
size_t hs = hash(i, m);
if (hs == hfind)
{
if (strncmp(i, find, m) == 0)
{
p = i;
break;
}
}
}
}
}

return p;
}

最佳答案

您没有正确实现散列。 Rabin-Karp 的关键是随着潜在匹配沿着要搜索的字符串移动,增量更新散列。正如您所确定的那样,如果您为每个可能的匹配位置重新计算整个哈希值,事情将会非常缓慢。

对于除第一次比较之外的每种情况,您的哈希函数都应采用现有哈希、一个新字符和一个旧字符,并返回更新后的哈希。

关于c++ - Rabin-Karp 算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/10256913/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com