gpt4 book ai didi

java - Rabin-Karp算法Java的滚动哈希算法

转载 作者:塔克拉玛干 更新时间:2023-11-03 03:51:36 28 4
gpt4 key购买 nike

我一直在尝试理解算法类的 Rabin-Karp 算法。我在理解它时遇到了很多麻烦,所以我尝试实现它(我实际上不必实现它)。我想我正确地理解了滚动哈希函数以外的所有内容。我的算法目前只适用于模式 char[] 在文本 char[] 开头匹配的情况。我不知道我的滚动哈希哪里出了问题。如果有人可以指出错误的方向,我将非常感激。

结果文本“我的测试字符串”模式“我的” - 这回来匹配模式“测试”- 这显示不匹配

private static int int_mod(int a, int b)
{
return (a%b +b)%b;
}

public static int rabin_Karp(char[] text, char[] pattern)
{
int textSize = text.length;
int patternSize = pattern.length;
int base = 257;
int primeMod = 1000000007;

if(textSize < patternSize)
return -1;n
int patternHash = 0;
for(int i = 0; i < patternSize; i++)
patternHash += int_mod(patternHash * base + pattern[i], primeMod);//This is only done once so put method here
System.out.println("patternHash: " + patternHash);
//calculate the value of the first hash
int segmentHash = 0;
for(int i = 0; i < patternSize; i++) //remove this, this will be duplicate
segmentHash += int_mod(segmentHash * base + text[i], primeMod);
System.out.println("segmentHash: " + segmentHash);

Boolean firstMatch = false;
if(segmentHash == patternHash)
{
firstMatch = true;
for(int i=0; i<pattern.length; i++)
{
if(pattern[i] != text[i])
firstMatch = false;
}
}
if (firstMatch == true)
{
return 0;
}

for(int i=1; i<textSize - patternSize; i++)
{
segmentHash += int_mod(segmentHash * base + text[i + pattern.length -1],primeMod);
segmentHash -= int_mod(segmentHash * base + text[i-1], primeMod);
System.out.println("segmentHash: " + segmentHash);

if(segmentHash == patternHash)
{
firstMatch = true;
for(int j=0; j<pattern.length; j++)
{
if(pattern[j] != text[j])
firstMatch = false;
}
}
if (firstMatch == true)
{
return i;
}
}

return -1;
}

最佳答案

您的代码中存在几个基本问​​题。

第一个在这里:patternHash += int_mod(patternHash * base + pattern[i], primeMod); 它在其他几个地方重复。

第二个是计算划船哈希:

    segmentHash += int_mod(segmentHash * base + text[i + pattern.length -1],primeMod);
segmentHash -= int_mod(segmentHash * base + text[i-1], primeMod);

这两个错误都可以轻松修复。但是,我会建议您更好地理解代码背后的逻辑,而不是仅仅从某个地方复制它。您使用的散列算法是基于多项式的,因此请尝试查看该级别上发生的情况。甚至可以手写一些示例——它们在调试代码时会很有用。

另请注意,您将遇到整数溢出问题:
- int 可以存储高达 20 亿的数字;
- 你的 prime 模块大约有 10 亿,所以哈希值(特别是 patternHashsegmentHash)可以达到这个数字;
- 你的基础是 int base = 257;

因此,表达式 segmentHash * base 可以达到 ~2570 亿,这肯定是整数溢出。

关于java - Rabin-Karp算法Java的滚动哈希算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/18604247/

28 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com