RF 算法的全称叫 Rabin-Karp 算法,是由它的两位发明者 Rabin 和 Karp 的名字来命名的。
    RF 算法可以看成是 BF 算法的升级版。
    BF 算法中每次检查主串和子串是否匹配,都需要依次比对每个字符,所以 BF 算法的时间复杂度比较高。
    而 RF 算法通过哈希算法对主串中的 n-m+1 个子串分别求哈希值,然后逐个与模式串的哈希值比较大小,如果某个子串与模式串相等,那就说明对应的子串和模式串匹配了。
    image.png

    现在问题变成如何设计哈希算法对子串和模式串进行哈希计算。

    十进制表示法:

    1. 657 = 6*10*10 + 5*10 + 7*1

    假设字符串中只包含 a ~ z 26个字母,设计一个 26 进制,并且直接将字母直接映射到数字:

    1. cba = c*26*26 + b*26 + c*1
    2. = 2*26*26 + 1*26 + 0*1
    3. = 1353