[使用散列搜索另一个字符串中的子字符串

Question

这是代码。

它给我一个错误的结果

h [n2-1]应该存在于集合中，但不是

代码中的错误应该在哪里？

注意：当我使用模块化逆而不是p [i-8]的倍数时，代码运行良好。

代码说明：

我正在将“ p = 31”的前n个幂存储在数组中。

为数组0中的s的每个子字符串存储0-> i子串

从'h'数组计算长度为9的每个哈希，并将其存储在集合中。

组中的打印哈希。

我正在对字符串t进行哈希处理并存储其哈希值。

打印t的哈希。

比较集合中t和散列的哈希。

我在t中找不到哈希。

#include <bits/stdc++.h>

#define m 1000000007
#define N (int)2e6 + 3

using namespace std;

long long pows[N], h[N], h2[N];

set<int> ss;

int main()
{

string s = "www.cplusplus.com/forum";

// powers array
pows[0] = 1;
int n = s.length(), p = 31;
for(int i = 1; i < n; i++){
    pows[i] = pows[i-1]*p;
    pows[i] %= m;
}

// hash from 0 to i array
h[0] = s[0]-'a'+1;
for(int i = 1; i < n; i++){
    h[i] = h[i-1] + (s[i]-'a'+1)*pows[i];
    h[i] %= m;
}

// storing each hash with 9 characters in a set
ss.insert(h[8]);
for(int i = 9; i < n; i++){
    int tp = h[i] - h[i-9]*pows[i-8];
    tp %= m;
    tp += m;
    tp %= m;
    ss.insert(tp);
}

// print hashes with 9 characters
set<int>::iterator itr = ss.begin();
while(itr != ss.end()){
    cout << *(itr++) << " ";
}
cout << endl;

// t is the string that i want to check if it is exist in s
string t = "cplusplus";
int n2 = t.length();
h2[0] = t[0]-'a'+1;
for(int i = 1; i < n2; i++){
    h2[i] = h2[i-1] + (t[i]-'a'+1)*pows[i];
    h2[i] %= m;
}
// print t hash
cout << h2[n2-1] << endl;

return 0;
}

Answer 1

我可以看到您的代码有两个问题：

1. [当您计算长度为9的子字符串的哈希时，会将中间结果（类型为long long）存储在int变量中。这可能会导致整数溢出，并且您计算的哈希可能不正确。
2. 给出字符串s = {s[0], s[1], ..., s[n-1]}，计算哈希的方式是：h = ∑ s[i] * p^i。在这种情况下，给定前缀哈希存储在h中，子字符串s[l..r]（含）的哈希应为(h[r] - h[l - 1]) / p^(r-l+1)，而不是您编写的内容。这也是为什么使用模逆（模逆除法）是正确的原因。

我认为计算散列的更常见方法是另一种方法，即h = ∑ s[i] * p^(n-i-1)。这使您可以将子字符串哈希计算为h[r] - h[l - 1] * p^(r-l+1)，而无需计算模块化逆。