Rabin-Karp算法预计算哈希与多项式哈希值不匹配问题排查

问题现象 #

用C++实现Rabin-Karp字符串匹配算法后，测试用例执行失败：

• 模式串：aab
• 文本串：abxaabbbaaab
  直接调用PolynomialHash计算子串哈希能得到预期匹配索引[3,9]，但使用预计算的哈希值时，仅能命中索引9，索引3的哈希值不匹配。

核心问题分析 #

对比代码后发现两个关键不一致点：

1. 字符映射规则不一致 #

PolynomialHash函数直接使用字符的原始ASCII值参与哈希计算：

hash_val = (hash_val*x+str[i])%prime;

但预计算哈希时使用的是GetInt(text[i])（即字符-'a'的偏移值）：

substring_hashes[i] = (prime + substring_hashes[i+1]*x + GetInt(text[i]) - y*GetInt(text[i+pattern_len]))%prime;

两种方式的数值差异直接导致哈希结果完全不同。

2. 哈希计算顺序相反 #

PolynomialHash是从子串的末尾到开头遍历计算：

for(int i = ei;i>=si;i--) hash_val = (hash_val*x+str[i])%prime;

对应的哈希公式为：
hash = s[ei] + s[ei-1]*x + s[ei-2]*x² + ... + s[si]*x^(ei-si)

而预计算哈希的递推公式是基于从左到右的哈希规则设计的，对应的公式为：
hash = s[si]*x^(len-1) + s[si+1]*x^(len-2) + ... + s[ei]
两种哈希的编码逻辑完全相反，导致预计算值和直接计算值无法匹配。

修复方案 #

步骤1：统一字符映射规则 #

修改PolynomialHash，用GetInt(str[i])代替原始字符值，和预计算逻辑对齐：

ll PolynomialHash(const string &str,ll prime,ll x,int si,int ei){
    ll hash_val = 0; 
    for(int i = ei;i>=si;i--) {
        hash_val = (hash_val*x + GetInt(str[i]))%prime;
    }
    return hash_val;
}

步骤2：对齐哈希计算顺序 #

如果要保留原PolynomialHash的从右到左计算逻辑，需要修改预计算的递推公式。或者更简单的方式是修改PolynomialHash为从左到右计算，适配原预计算公式：

ll PolynomialHash(const string &str,ll prime,ll x,int si,int ei){
    ll hash_val = 0; 
    for(int i = si;i<=ei;i++) {
        hash_val = (hash_val*x + GetInt(str[i]))%prime;
    }
    return hash_val;
}

同时，预计算函数中初始化最后一个子串哈希的代码会自动使用修改后的PolynomialHash，确保初始值正确。

验证 #

修改完成后，预计算的哈希值会和直接调用PolynomialHash的结果完全一致，测试用例将正确匹配索引3和9。

内容的提问来源于stack exchange，提问作者Pawan Nirpal