В моем назначении для строки S мне нужно сравнить две подстроки одинаковой длины. Выходные данные должны быть "Yes", если они равны, "No", если они не равны. Мне даны начальные индексы двух подстрок (a и b) и длина подстрок L.
Например, для S = "Hello", a = 1, b = 3 , L = 2, подстроки: substring1 = "el" и substring2 = "lo", которые не равны, поэтому ответ будет "No".
Я думаю, хэширование каждой подстроки основной строки S и записать их все в память было бы хорошим подходом. Вот код, который я написал для этого (я попытался реализовать то, что узнал об этом из курса Coursera, который я проходил):
Эта функция принимает любую строку и значения для p и x для хеширования, и выполняет полиномиальное ха sh для данной строки.
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 столбцов (половина из которых теряется, потому что я не мог найти, как правильно заставить его работать как треугольник, поэтому мне пришлось go для полного прямоугольника angular массив). Предполагая, что n = 7, тогда ah[0]-ah[6] являются значениями ha sh для string[0]-string[6] (что означает все подстроки длины 1). ah[7]-ah[12] - это значения ha sh для string[0-1]-string[5-6] (что означает все подстроки длины 2) и т. Д. c. до конца.
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 - как какое-то «случайное» простое число, выбранное вручную. Я беру текст в качестве ввода, инициализирую массив ha sh, заполняю массив ha sh, а затем беру запросы в качестве ввода, чтобы ответить на все запросы из моего массива.
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 ограничение по времени, которое довольно мало для просмотра символов по одному для каждой строки.