c++ - 使用散列等长比较的子字符串

Question

在我拥有的分配中，对于字符串S，我需要比较两个长度相等的子字符串。如果它们相等，则输出应为"Yes"，如果不相等，则输出应为"No"。给我两个子字符串(a和b)的起始索引，以及子字符串L的长度。

例如，对于S = "Hello"，a = 1，b = 3，L = 2，子字符串为:substring1 = "el"和substring2 = "lo"不相等，因此答案将是"No"。

我认为散列主字符串S的每个子字符串并将它们全部写入内存将是一个很好的方法。这是我为此编写的代码(我尝试实现从我正在参加的Coursera类(class)中学到的知识):

此函数接受任何字符串，并将p和x的值用于哈希事物，然后对给定的字符串执行多项式哈希。

long long PolyHash(string str, long long p, int x){
    long long res = 0;
    for(int i = str.length() - 1; i > -1; i--){
        res = (res * x + (str[i] - 'a' + 1)) % p;
    }
    return res;
}

下面的函数只是预先计算所有哈希，并填充一个称为 ah的数组，该数组在主函数中初始化。数组 ah由 n = string length行和 n = string length列组成(其中一半浪费了，因为我找不到如何使其正确地用作三角形，因此必须使用完整的矩形数组)。假设 n = 7，则 ah[0]-ah[6]是 string[0]-string[6]的哈希值(意味着所有长度为1的子字符串)。 ah[7]-ah[12]是 string[0-1]-string[5-6](意味着长度为2的所有子字符串)的哈希值，依此类推，直到末尾。

void PreComputeAllHashes(string str, int len, long long p, int x, long long* ah){
    int n = str.length();
    string S = str.substr(n - len, len);
    ah[len * n + n - len] = PolyHash(S, p, x);
    long long y = 1;
    for(int _ = 0; _ < len; _++){
        y = (y * x) % p;
    }
    for(int i = n - len - 1; i > -1; i--){
        ah[n * len + i] = (x * ah[n * len + i + 1] + (str[i] - 'a' + 1) - y * (str[i + len] - 'a' + 1)) % p;
    }
}

下面是主要功能。我把 p等于一些大质数，而 x则是手工挑选的，有些“随机”的质数。
我将文本作为输入，初始化哈希数组，填充哈希数组，然后将查询作为输入，以回答数组中的所有查询。

int main(){
    long long p = 1e9 + 9;
    int x = 78623;
    string text;
    cin >> text;
    long long* allhashes = new long long[text.length() * text.length()];
    for(int i = 1; i <= text.length(); i++){
        PreComputeAllHashes(text, i, p, x, allhashes);
    }
    int queries;
    cin >> queries;
    int a, b, l;
    for(int _ = 0; _ < queries; _++){
        cin >> a >> b >> l;
        if(a == b){
            cout << "Yes" << endl;
        }else{
            cout << ((allhashes[l * text.length() + a] == allhashes[l * text.length() + b]) ? "Yes" : "No") << endl;
        }
    }
    return 0;
}

但是，在Coursera上进行此分配的测试用例之一抛出了这样的错误:
Failed case #7/14: unknown signal 6 (Time used: 0.00/1.00, memory used: 29396992/536870912.)
我在网上查询了以下内容:

Unknown signal 6 (or 7, or 8, or 11, or some other).This happens when your program crashes. It can be
because of division by zero, accessing memory outside of the array bounds, using uninitialized
variables, too deep recursion that triggers stack overflow, sorting with contradictory comparator,
removing elements from an empty data structure, trying to allocate too much memory, and many other
reasons. Look at your code and think about all those possibilities.

而且我整天都在看我的代码，但仍然无法为该错误提供解决方案。任何帮助解决此问题的方法将不胜感激。

编辑:赋值状态指出输入字符串的长度最多可以为 500000个字符，而查询数则最多可以为 100000。此任务还具有 1 second时间限制，对于每个字符串一个接一个地检查字符来说，这个时间限制非常小。

Answer 1

因此，我对如何降低实现的算法的复杂性进行了一些研究，终于找到了它!事实证明，给定初始字符串的前缀散列，有一种 super 简单的方法(嗯，如果您不考虑其背后的理论，则不是)可以获取任何子字符串的散列值!

您可以阅读有关它的更多信息here，但是我将尝试简要地解释一下。

那么我们该怎么做-我们预先计算前缀子字符串的所有哈希值。
字符串"hello"的前缀子字符串如下:

h
he
hel
hell
hello

一旦有了所有这些前缀子字符串的哈希值，就可以将它们收集在 vector 中，使得:
h[str] = str[0] + str[1] * P + str[2] * P^2 + str[3] * P^3 + ... + str[N] * P^N
其中P是任何质数(我选择了 p = 263)
然后，我们需要一个较高的值，我们将对所有值取模，以使事情不会太大。我将选择 m = 10^9 + 9这个数字。

首先，我创建一个 vector 来保存 P的预先计算出的幂:

vector<long long> p_pow (s.length());
p_pow[0] = 1;
for(size_t i=1; i<p_pow.size(); ++i){
    p_pow[i] = (m + (p_pow[i-1] * p) % m) % m;
}

然后，我计算前缀子字符串的哈希值 vector :

vector<long long> h (s.length());
for (size_t i=0; i<s.length(); ++i){
    h[i] = (m + (s[i] - 'a' + 1) * p_pow[i] % m) % m;
    if(i){
        h[i] = (m + (h[i] + h[i-1]) % m) % m;
    }
}

假设我有 q查询，每个查询由3个整数组成: a， b和 L。

为了检查子串 s1 = str[a...a+l-1]和 s2 = str[b...b+l-1]的相等性，我可以比较这些子串的哈希值。为了使用刚刚创建的具有前缀子字符串的值获取子字符串的哈希值，我们需要使用以下公式:

H[I..J] * P[I]  =  H[0..J]  -  H[0..I-1]

同样，您可以在链接中阅读有关此内容的证明。

因此，要解决每个查询，我将执行以下操作:

cin >> a >> b >> len;
if(a == b){      // just avoid extra calculation, saves little time
    cout << "Yes" << endl;
}else{
    long long h1 = h[a+len-1] % m;
    if(a){
        h1 = (m + (h1 - h[a-1]) % m) % m;
    }
    long long h2 = h[b+len-1] % m;
    if(b){
        h2 = (m + (h2 - h[b-1]) % m) % m;
    }
    if (a < b && h1 * p_pow[b-a] % m == h2 % m || a > b && h1 % m == h2 * p_pow[a-b] % m){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
}