string - 如何在 Rabin Karp 算法的滚动哈希中加入 mod?
问题描述
我正在尝试用 mod 实现 Rabin Karp 算法。我正在使用的哈希函数是:
H1= c1*a^k-1 + c2*a^k-2 +c3*a^k-3 +…+ck*a^0
这里 cx 是字符的 ASCII 值。为了滚动它,我首先通过减去它来删除第一项,然后乘以 a 并通过将它乘以 a^0 来添加新项。
现在的问题是处理我使用过 mod 操作的大值,但这样做我无法正确滚动它。我的代码如下:
public class RabinKarp {
private static final int base = 26;
private static final int mod = 1180637;
public static void main(String[] args) {
String text = "ATCAAGTTACCAATA";
String pattern = "ATA";
char[] textArr = text.toCharArray();
char[] patternArr = pattern.toCharArray();
System.out.println(getMatchingIndex(textArr, patternArr));
}
public static int getMatchingIndex(char[] textArr, char[] patternArr) {
int n = textArr.length;
int m = patternArr.length;
int patternHash = getHashForPatternSize(patternArr, m);
int textHash = getHashForPatternSize(textArr, m);
for(int i = 0; i < n-m; i++) {
if(patternHash == textHash && checkMatch(textArr, patternArr, i, m))
return i;
textHash = rollingHash(textArr, textHash, i, m);
}
return -1;
}
public static boolean checkMatch(char[] textArr, char[] patternArr, int i, int m) {
for(int j = 0; j < m; j++,i++) {
if(textArr[i] != patternArr[j])
return false;
}
return true;
}
public static int rollingHash(char[] textArr, int textHash, int i, int m) {
return (textHash * base - modularExponentiation(base, m, mod) * (int)textArr[i] + (int) textArr[i+m])%mod;
}
public static int getHashForPatternSize(char[] arr, int m) {
int hash = 0;
for(int i = 0, p = m; i < m; i++, p--) {
hash = (hash%mod + calcHash(arr[i], p)%mod)%mod;
}
return hash;
}
public static int calcHash(char alphabet, int p) {
return (((int) alphabet)%mod * modularExponentiation(base, p, mod)%mod)%mod;
}
public static int modularExponentiation(int base, int p, int mod) {
if(p == 0)
return 1;
if(p%2 == 0)
return modularExponentiation((base*base)%mod, p/2, mod);
else
return (base*modularExponentiation((base*base)%mod, (p-1)/2, mod))%mod;
}
}
问题是,textHash
在patternHash
任何时候都不匹配。我确信问题出在 mod 操作上。任何人都可以告诉如何拥有 mod 以及正确使用滚动哈希。我将非常感谢。
解决方案
计算 Rabin-Karp 滚动哈希的常用方法是以大端顺序考虑字符,而不是小端解决方案。这使得算术更容易,因为它避免了除法。模块化除法很重要,您不能简单地将其实现为(p/q)%b
.
如果我们将滚动哈希作为
H0…k-1 = (c0*ak-1 + c1*ak-2 + c2*ak-3 …+… ck-1*a0) mod b
那么下一个术语是:
H1…k = ( c1*ak-1 + c2*ak-2 …+… ck-1*a1 + ck*a0) mod b
我们可以很容易地看到
H1…k = (a * H0…k-1 - c0*ak + ck) mod b
如果我们然后 precompute ,则变为:m == ak mod b
H1…k = (a * H0…k-1 - m * c0 + ck) mod b
每次迭代的工作量要少得多,并且根本不依赖于除法。
推荐阅读
- ruby-on-rails - 由于资产管道错误,无法在 Heroku 上部署 Rails 应用程序
- python-3.x - 如何使用 doctest 测试异步函数?
- php - Laravel 7 自定义助手在登录时呈现我的应用程序抛出异常(页面已过期)
- r - 使用 ggplot2 绘制变量的平均值
- typescript - 打字稿:使用字符串的子集作为[key:subset]
- c++ - Google 测试 - 未定义对 testing::internal::AssertHelper::AssertHelper 的引用
- reactjs - 使用 Object.entries 检索值时,如何在 typescript react 应用程序中正确键入从 JSON 对象(api 调用)检索的空值?
- r - 如何在 Windows 10 中安装“不可用”的 R 包(MCMCpack)?
- javascript - 尝试在 React JS 中破坏数组时显示错误
- regex - 如何使用 Powershell 打印包含匹配字符串的整个函数?