c - Rabin-Karp 字符串搜索算法

Question

我的 previous question属于通用字符串搜索算法。我正在研究 Rabin-Karp 算法，我有一个函数模板，例如:

RabinKarpMatch(char *Text, char *Search_phrase,int radix,int prime)

我想知道 radix 和 prime 的值将如何根据 search_phrase 和文本而变化？或者我应该为所有情况只给它们任意值？

Answer 1

在 Rabin-Karp 算法中，基数和素数在文本处理过程中不会改变。但是选择好的基数和素数至关重要。在最坏的情况下(在实践中几乎不可能)，当文本的所有子字符串都具有与模板哈希码相同的哈希码时，算法将在 O(nm) 时间内运行，其中 n 是文本长度，m 是模板长度。

一般规则:Prime - 必须小，radix - 必须方便使用。我相信对像:

(质数，基数)

31, 2^64

37, 2^64

57, 2^64

对你来说没问题。

在一些实现中，为了最小化散列冲突，使用了不止一对。