子字符串查找----Rabin-Karp算法（基于散列）
子字符串查找----Rabin-Karp算法（基于散列）
SuperHeroes
发布于 2018-05-30 17:58:11
发布于 2018-05-30 17:58:11
Rabin-Karp算法是一种基于散列的子字符串查找算法--先计算模式字符串的散列值，然后用相同的散列函数计算文本中所有可能的M个字符的子字符串的山裂纸并与模式字符串的散列值比较。如果两者相同，再继续验证两者是否匹配。
基本思想：长度为M的对应着一个R进制的M位数，
举例说明Rabin-Karp算法：
例如要在文本3141592653589793中找到模式26535，首先选择散列表大小Q（这里设置为997），采用除留余数法，散列值为26535%997 = 613，然后计算文本中所有长度为5的字符串的散列值并寻找匹配。
关键思想：实现Rabin-Karp算法关键是要找到一种方法能够快速地计算出文本中所有长度等于要匹配字符串长度的子字符串的散列值。也就是对所有位置i, 高效计算出文本中i+1位置的子字符串的值。具体算法为：假设已知h(xi) = xi mod Q, 将模式字符串右移一位等价于将xi替换为x(i+1), x(i+1)等于xi减去第一个数字的值，乘以R，再加上最后一个数字的值。这么做的结果是无论M是5、100还是1000，都可以在常数时间内不断地一格一格向后移动。
计算散列函数：对于5位的数，可以用int直接计算，但如果M等于100、1000就不行了。这时候可以使用Horner方法。其计算方法如下：
private long hash(String key, int m) {
long h = 0;
for (int j = 0; j < m; j++)
h = (R * h + key.charAt(j)) % q;
return h;
}查找实现：有两种代表实现：蒙特卡洛方法和拉斯维加斯方法。
蒙特卡洛方法是选取很大的Q值，使得散列冲突极小，这样可以保证散列值相同就是匹配成功；
拉斯维加斯方法则是散列值相同后再去比较字符，效率不如上一种方法，但可以保证正确性。
public class RabinKarp {
private String pat;
private long patHash;
private int m;
private long q;
private int R;
private long RM;
public RabinKarp(String pat) {
this.pat = pat;
R = 256;
m = pat.length();
q = longRandomPrime();
RM = 1;
for (int i = 1; i <= m-1; i++)
RM = (R * RM) % q;
patHash = hash(pat, m);
}
private long hash(String key, int m) {
long h = 0;
for (int j = 0; j < m; j++)
h = (R * h + key.charAt(j)) % q;
return h;
}
private boolean check(String txt, int i) {
for (int j = 0; j < m; j++)
if (pat.charAt(j) != txt.charAt(i + j))
return false;
return true;
}
public int search(String txt) {
int n = txt.length();
if (n < m) return n;
long txtHash = hash(txt, m);
if ((patHash == txtHash) && check(txt, 0))
return 0;
for (int i = m; i < n; i++) {
txtHash = (txtHash + q - RM*txt.charAt(i-m) % q) % q;
txtHash = (txtHash*R + txt.charAt(i)) % q;
int offset = i - m + 1;
if ((patHash == txtHash) && check(txt, offset))
return offset;
}
return n;
}
private static long longRandomPrime() {
BigInteger prime = BigInteger.probablePrime(31, new Random());
return prime.longValue();
}
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2018.01.26，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读