Rabin-Karp字符串匹配算法

除了相互的字条串匹配算法外，Rabin-Karp字符串匹配算法也能很好的运行，其预处理时间为O(m),在最坏运行情况下运行时间为O（n-m+1）,期望的匹配时间为O（n）。

基本原理如下：

选择一个素数，对模式串和待处理串，进行取余处理（长度为模式串的长度），这就是预处理过程，然后以模式串的余数去和待处理串处理的余数进行对比，如果相同，则可能是匹配的地方，但可能出现伪匹配的时候，还要进行二次判断。其中在对待处理串进行取余处理时，可以采用霍纳法则。

参考：算法导论。