Rabin-Karp 算法(字符串快速查找)

Go 语言的 strings 包(strings.go)中用到了 Rabin-Karp 算法。Rabin-Karp 算法是基于这样的思路:即把字符串看作是字符集长度进制的数,由数值的比较结果得出字符串的比较结果。朴素的字符串匹配算法为什么慢?因为它太健忘了,前一次匹配的信息其实有部分可以应用到后一次匹配中去,而朴素的字符串匹配算法只是简单的把这个信息扔掉,从头再来,因此,浪费了时间。好好的利用这些信息,自然可以提高运行速度。由于完成两个字符串的比较需要对其中包含的字符进行逐个比较,所需的时间较长,而数值比较则一次就可以完成,那么我们首先把“搜索词”中各个字符的“码点值”通过计算,得出一个数值(这个数值必须可以表示出字符的前后顺序,而且可以随时去掉某个字符的值,可以随时添加一个新字符的值),然后对“源串”中要比较的部分进行计算,也得出一个数值,对这两个数值进行比较,就能判断字符串是否匹配。对... Read More