在替换字符串中的单个字符时修改哈希值 (c++)

Question

我正在使用多项式哈希函数来计算字符串（仅由小写英文字母组成）的哈希值，如下所示：

int SZ = 105, P = 31;
long long M = 1e12 + 9;
vector <long long> pw;

pw.resize(SZ, 1);
for(int i = 1; i < SZ; i++) {
   pw[i] = (pw[i - 1] * P) % M;
}

long long calculateHash(string &s) {
    long long h = 0;
    
    for(int i = 0; i < s.length(); i++) {
        h = (h + (s[i] - 'a' + 1) * pw[i]) % M;
    }
    
    return h;
}

我不想在 O(N) 时间内重新计算整个字符串的散列，因为我必须只替换任何给定位置的一个字符。因此，为了在 O(1) 时间内完成此操作，我执行以下操作：

long long h1 = calculateHash(s1);
long long h2 = calculateHash(s2);

// Only one character differs in `s1` and `s2` at index `idx`

// Modifying hash for h1 to incorporate s2[idx] and removing s1[idx]
h1 = (h1 + ((s2[idx] - s1[idx]) * pw[idx])) % M;

现在我检查h1 == h2，理想情况下应该是相等的，对吧？它确实适用于较小的字符串，但有时会失败，我得到 h1 的负值，不确定这是溢出问题还是 ((s2[idx] - s1[idx]) * pw[idx]) 更负导致 h1 低于零。

任何人都可以建议一种在仅更改一个字符的情况下在 O(1) 时间内重新计算哈希的方法吗？提前致谢！

Answer 1

原则上你改变结果值的想法是正确的，但你需要的是一个模运算符，它的结果总是正的，对于负输入数字也是如此。

要使用 C++ 模模拟此行为，您可以执行以下操作：

long long tmp=(h1 + ((s2[idx] - s1[idx]) * pw[idx])) % M;
h1=(tmp+M)%M;

第一行是你做的相同操作，第二行使结果为正，因为在 C++ 模运算后 tmp 不能小于 -M。需要额外的模数来确保数字保持小于 M，即使 tmp 已经是正数。

在替换字符串中的单个字符时修改哈希值 (c++)

Modify hash value on replacing a single character in string (c++)

c++

string

hash

polynomials