RK字符串查找算法

算法描述

  • RK算法是一种基于散列的算法:计算pat的散列函数,用相同函数计算txt中所有可能的M个字符的字符串散列值,寻找匹配

实现

  • 计算散列函数:Horner方法—除留余数法计算散列值
  1. private long hash(String key, int M){
  2.     long h = 0;
  3.     for (int j = 0; j < M; j++)
  4.         h = (R*h + key.charAt(j)) % Q;
  5.     return h;
  6. }

问题:算法不会生成散列表,需要实时计算散列值比较,若每次都接收一个key在计算,开销最坏依旧为NM和暴力法一致

改进:利用i位散列值,计算i+1位散列值

  • txt中i位起始的M个字符散列值:减去LSD,乘R,加上新的MSD
    1. 转换为R进制数:X=tR+tR+…+tR
    2. x = (x-tR)R+t
    3. h(x)=xmodQ
    • 以上操作可分步求模:分步求模等价与所有运算后求模,且实际运算加上Q保证结果为正
  1. private int search(String txt){
  2.     int N = txt.length();
  3.     long txtHash = hash(txt, M);//注意为M
  4.     if (patHash == txtHash) return 0;//初始就匹配成功
  5.     for (int i = M; i < N ; i++){
  6.         txtHash = (txtHash + Q - RM * txt.charAt(i-M) % Q) % Q;
  7.         txtHash = (txtHash*R + txt.charAt(i)) % Q;
  8.         if (txtHash == patHash) return i-M+1;//找到匹配
  9.     }
  10.     return N;//未找到
  11. }
  • 正确性:当散列值相等后,在没有构建散列表的情况下为了避免散列值冲突可能会再次比较两个字符串是否一致,但若令Q为大于10,冲突概率小于10,叫做蒙特卡洛算法
  1. public class RabinKarp {
  2.     private long patHash;
  3.     private int M;
  4.     private long Q;//一个很大素数
  5.     private int R;
  6.     private long RM;//减去第一个数字
  8.     public RabinKarp(String pat){}
  10.     private long hash(String key, int M){}
  12.     private int search(String txt){}
  13. }

RK.png

算法分析

  • 当Q采取很大素数时,RK算法可以在接近线性级别且保持准确性的查找字符串,被称为指纹查找,因其可以将极大的pat转换为极少的信息hashcode进行查找