1.什么是Rabin-Karp算法
什么是Rabin-Karp算法，它是一个常见的字符串匹配算法，通常学过数据结构的人知道，常见的字符串匹配算法有BF，KMP算法，其中KMP算法性能是比较优良的，在这里讲的是Rabin-Karp（简称RK）算法，性能也是很好的，利用了hashcode的思想，将比较的字符串进行求hashcode的值，我们知道，若两个字符不同，他们的hashcode值可能相同（几率很小），若两者hashcode值不同，必推出两个字符串不同，所以利用这个思想就设计了RK算法。
2.RK算法解析
现在举个例子假如有两个字符串，T和P，T为主串，P为待匹配的模式串
T和P串都是待匹配的数值字符串，虽然都是数字，但都是字符型数字。那么这里就采取如下步骤来解决该字符串匹配问题
- 分别计算T串前四位的hashcode值和P串的hashcode值,其中我们可以引入一个权值r=10，来计算着几位字符串的hashcode,其中 "1256"的hashcode值为tval=('1'-'0')*10^3+('2'-'0')*10^2+('5'-'0')*10^1+('6'-'0')*10^0=1256,同理"5689"的hashchode值为pval=5689
- 计算pval与tval的值是否相同，若不同，则T的下一次要求的字符串为"2568"，即整体字符串往左移动一位，这样新得到的hashcode值怎么计算啊，是否为上一步的tval=(tval-('1'-'0')*h)*r+('8'-'0') (这里h代表最高位的n次幂的值，即h=10^3)。总的来说就是上一次的值，减去最高位的值乘以权值，然后再加上最低位的值。
- 再一次比较pval和tval的值，若相同，则说明匹配成功，否则则匹配失败，匹配失败则会继续上一步操作，直到T的待匹配字符串长度小于p的字符串长度，这标记匹配失败
3.RK的算法引入的问题
由刚才的算法可知，会有几个问题需要考虑：
- 若待匹配字符串长度过长，权值过大，那么求得的hashcode值必会导致溢出，现有的数据类型不能保存的问题
- 若hashcode取值过大通常会考虑模一个素数，虽然解决了溢出问题，但是会导致hash冲突
所以为了解决以上两个问题，我们需要改进以上算法，未完待续