Напишите функцию, правильно реализующую алгоритм Рабина карпа
Мне поручено написать функцию, которая реализует алгоритм Рабина карпа с одним текстом и массивом списка возможных паттернов. Шаблон представляет собой массив из k указателей, а длина текста равна m. Результат не прошел предусмотренную тестовую функцию. Я не могу понять, в чем ошибка. Может ли кто-нибудь сказать мне, где находятся ошибки или как я могу написать другую тестовую функцию, чтобы увидеть, что я возвращаю здесь, чтобы я мог сравнить ее с правильной?
Что я уже пробовал:
int substring(char * text, int k, int m, char* patterns[]) { int hp = 0; // hash value of pattern int t = 0; // hash value of text int h = 0; int i , j; int p = 1009; //prime number > 1000 int d = 256; // random base of polynomial text[200]; char pat[100]; for (i = 0; i < k - 1; i++) h = (h*d) % p; //hash value of pattern and hash value of the compared text substring for (i = 0; i < k; i++) { hp = (d*p + pat[i]) % p; t = (d*p + text[i]) % p; } //slide pattern over text for (i = 0; i <= m - k; i++) { if (hp == t) { for (j = 0; j < k; j++) { if (text[i+j] != patterns[j]) break; } if (j == k) return i; } if (i < m - k) { t = (d*(t - text[i] * h) + text[i+k]) % p; if (t < 0) t = (t + p); } } }
[no name]
В дополнение к решению 1, Не входите в привычку использовать односимвольные имена переменных. Вы можете вспомнить, для чего сегодня была использована буква "н", но на следующей неделе вы этого не сделаете. Если "p" - простое число, то сделайте переменную именем primeNumber, и вам не придется пытаться вспомнить, что это такое, и вам не нужно будет иметь дополнительный комментарий, чтобы напомнить вам, что это такое.