Q:

Substrings of equal length comparison using hashing

On an assignment that I have, for a string S, I need to compare two substrings of equal lengths. Output should be "Yes" if they are equal, "No" if they are not equal. I am given the starting indexes of two substrings (a and b), and the length of the substrings L.
For example, for S = "Hello", a = 1, b = 3, L = 2, the substrings are:
substring1 = "el" and substring2 = "lo", which aren't equal, so answer will be "No".
I think hashing each substring of the main string S and writing them all to memory would be a good aproach to take. Here is the code I have written for this (I have tried to implement what I learned about this from the Coursera course that I was taking):
This function takes any string, and values for p and x for hashing thing, and performs a polynomial hash on the given string.
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;
}

The function below just precomputes all hashes, and fills up an array called ah, which is initialized in the main function. The array ah consists of n = string length rows, and n = string length columns (half of which gets wasted because I couldn't find how to properly make it work as a triangle, so I had to go for a full rectangular array). Assuming n = 7, then ah[0]-ah[6] are hash values for string[0]-string[6] (meaning all substrings of length 1). ah[7]-ah[12] are hash values for string[0-1]-string[5-6] (meaning all substrings of length 2), and etc. until the end.
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;
    }
}

And below is the main function. I took p equal to some large prime number, and x to be some manually picked, somewhat "random" prime number.
I take the text as input, initialize hash array, fill the hash array, and then take queries as input, to answer all queries from my array.
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;
}

However, one of the test cases for this assignment on Coursera is throwing an error like this:
Failed case #7/14: unknown signal 6 (Time used: 0.00/1.00, memory used: 29396992/536870912.)
Which, I have looked up online, and means the following:
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.

And I've been looking at my code the entire day, and still haven't been able to come up with a solution to this error. Any help to fix this would be appreciated.
Edit: The assignment states that the length of the input string can be up to 500000 characters long, and the number of queries can be up to 100000. This task also has 1 second time limit, which is pretty small for going over characters one by one for each string.

A:

So, I did some research as to how I can reduce the complexity of this algorithm that I have implemented, and finally found it! Turns out there is a super-simple way (well, not if you count the theory involved behind it) to get hash value of any substring, given the prefix hashes of the initial string!
You can read more about it here, but I will try to explain it briefly.
So what do we do - We precalculate all the hash values for prefix-substrings.
Prefix substrings for a string "hello" would be the following:
h
he
hel
hell
hello

Once we have hash values of all these prefix substrings, we can collect them in a vector such that:
h[str]  =  str[0]  +  str[1] * P  +  str[2] * P^2  +  str[3] * P^3  +  ...  +  str[N] * P^N
where P is any prime number (I chose p = 263)
Then, we need a high value that we will take everything's modulo by, just to keep things not too large. This number I will choose m = 10^9 + 9.
First I am creating a vector to hold the precalculated powers of 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;
}

Then I calculate the vector of hash values for prefix substrings:
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;
    }
}

Suppose I have q queries, each of which consist of 3 integers: a, b, and L.
To check equality for substrings s1 = str[a...a+l-1] and s2 = str[b...b+l-1], I can compare the hash values of these substrings. And to get the hash value of substrings using the has values of prefix substrings that we just created, we need to use the following formula:
H[I..J] * P[I]  =  H[0..J]  -  H[0..I-1]

Again, you can read about the proof of this in the link.
So, to address each query, I would do the following:
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;
    }
}

