/** * rk字符串匹配算法,主要引入了hash的概念, * 利用子串的hash值依次对比主串相应长度的子串hash值 * 并对hash值相同的子串进行匹配对比 */ public class RKSearch { /** * rk算法入口 * @param t 主字符串 * @param p 子字符串 * @return */ public int rk(String t,String p){ // 字符串非法判定 if (t == null||t.length() == 0 || p == null || p.length() == 0 || p.length() > t.length()){ return -1; } // 计算子串hash值 int hash = hash(p,26,31,0,p.length()); for (int i = 0;i< t.length();i++){ // 对主串内的数字一次进行hash计算,并对比子串是否匹配 if (hash(t,26,31,i,p.length()) == hash && match(t,p,i)){ return i; } } return -1; } /** * 自定义hash算法 * @param str * @param r 进制数 * @param k 将字符串映射到k的范围 * @param start 从str串的开始位置 * @param len 子串的长度 * @return */ private int hash(String str,int r,int k,int start,int len){ int hash = 0; // 设定hash值为0 /** * 对字符串内的每个字符串进行计算 */ for (int i = start;i<start+len;i++){ // 进制系数 与 hash 的积 + 每个字符与范围取余的结果 hash = (r * hash + str.charAt(i) % k); } // 将最后的结果,映射到指定范围内 return hash % k; } /** * 对于hash计算结果相同的两个子串,是否匹配的比较 * 主要判定hash冲突情况下的匹配问题 * @param t 主串 * @param p 子串 * @param i 从主串下标为i的地方开始比较 * @return */ private boolean match(String t,String p,int i){ for (int j = 0 ; j < p.length();j++){ if (p.charAt(j) != t.charAt(j + i)){ return false; } } return true; } public static void main(String[] args) { String test = "adbsasdfddddsasdffesase"; String sub = "sd"; RKSearch rkSearch = new RKSearch(); int rk = rkSearch.rk(test, sub); System.out.println(rk); } }
标签:子串,hash,int,length,param,算法,字符串,java,rk From: https://www.cnblogs.com/shoshana-kong/p/17007141.html