对于我拥有的分配，对于字符串S，我需要比较两个长度相等的子字符串。如果它们相等，则输出应为"Yes"，如果不相等，则输出应为"No"。我得到了两个子字符串（a和b）的起始索引，以及子字符串L的长度。
例如，对于S = "Hello"，a = 1，b = 3，L = 2，子字符串为：substring1 = "el"和substring2 = "lo"不相等，所以答案将是"No"。
我认为对主字符串S的每个子字符串进行哈希处理并将它们全部写入内存将是一个很好的方法。这是我为此编写的代码（我尝试实现我从所修的Coursera课程中学到的知识）：
[此函数接受任何字符串，并将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时间限制，对于每个字符串一个接一个地检查字符来说，这个时间限制非常小。
因此，我进行了一些研究，以研究如何降低实现的算法的复杂度，并最终找到它！事实证明，给定初始字符串的前缀散列，有一种超级简单的方法（嗯，如果您不考虑其背后的理论，则不是）可以获取任何子字符串的哈希值！
您可以阅读有关它的更多信息here，但我将尝试简要地解释一下。
所以我们该怎么做-我们预先计算前缀子字符串的所有哈希值。字符串"hello"的前缀子字符串如下：
h
he
hel
hell
hello
一旦有了所有这些前缀子串的哈希值，我们就可以将它们收集在向量中，使得：
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。
首先，我创建一个向量来保存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<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]的相等性，我可以比较这些子字符串的哈希值。为了使用刚刚创建的前缀子字符串的has值获取子字符串的哈希值，我们需要使用以下公式：
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;
}
}
对于这样简单的任务，您的方法非常困难且复杂。假设您只需要执行一次此操作。您可以使用for循环手动比较子字符串。无需哈希。看一下这段代码：
for(int i = a, j = b, counter = 0 ; counter < L ; counter++, i++, j++){
if(S[i] != S[j]){
cout << "Not the same" << endl;
return 0;
}
}
cout << "They are the same" << endl;