Алгоритм Рабина-Карпа. В чем ошибка?

Question

[Никита]

Написал полиномиальную хэш-функцию без взятия остатка, может ли быть ошибка в этом? Алгоритм не проходит второй тест.

Задача:

Даны строки p и t. Требуется найти все вхождения строки p в строку t в качестве подстроки.
Формат входного файла
Первая строка входного файла содержит p, вторая t (1 <= |p|, |t| <= 10^6). Строки состоят из
букв латинского алфавита.
Формат выходного файла
В первой строке выведите количество вхождений строки p в строку t. Во второй строке выведите
в возрастающем порядке номера символов строки t, с которых начинаются вхождения p. Символы
нумеруются с единицы.

Мое решение:

#include <fstream>
#include <vector>
#include <string>

int x = 53;

int hash(const std::string& t, std::vector<int>& degree_x)
{
	int h = 0;
	for (int m = degree_x.size() - 2, i = 0; i < t.size(); m--, i++)
	{
		h += (t[i] - 'A' + 1) * degree_x[m];
	}
	return h;
}

bool equal(const std::string& t, const std::string& p)
{
	for (int i = 0; i < t.size(); i++)
	{
		if (t[i] != p[i])
			return false;
	}
	return true;
}

void buildH(std::string& t, std::string& p, std::vector<int>& H, std::vector<int>& degree_x)
{
	int n = t.size();
	int m = p.size();
	H[0] = hash(t.substr(0, m), degree_x);
	for (int i = 1; i < n - m + 1; i++)
	{
		H[i] = (H[i - 1] * x - (t[i - 1] - 'A' + 1) * degree_x.back() + (t[i + m - 1] - 'A' + 1));
	}
}

void Rabin_Karp(std::string& t, std::string& p, std::vector<int>& H, std::vector<int>& degree_x, std::vector<int>& answer)
{
	if (p.size() > t.size())
		return;
	buildH(t, p, H, degree_x);
	int hash_p = hash(p, degree_x);
	int n = t.size();
	int m = p.size();
	for (int i = 0; i < n - m + 1; i++)
	{
		if (H[i] != hash_p)
			continue;
		else if(equal(t.substr(i, m), p))
		{
			answer.push_back(i + 1);
		}
	}
}

int main()
{
	std::ifstream fin;
	std::ofstream fout;
	fin.open("search2.in");
	fout.open("search2.out");
	std::string p, t;
	fin >> p >> t;
	std::vector<int> degree_x;
	std::vector<int> answer;
	int val = 1;
 	for (int i = 0; i < p.size() + 1; i++)
	{
		degree_x.push_back(val);
		val *= x;
	}

	std::vector<int> H(t.size() - p.size() + 1, 0);
	Rabin_Karp(t, p, H, degree_x, answer);
	fout << answer.size() << '\n';
	for (auto el : answer)
	{
		fout << el << " ";
	}
	fin.close();
	fout.close();
	return 0;
}

Answer 1

[Wataru]

Возможно там переполнение. Убедитесь, что у вас все хеши везде считаются только с участием unsigned типов. Переполнение в signed - это Undefined behavior.

Comments

[Никита]

А как это можно проверить?

[Wataru]

Ну... Скормите ему большие строки. Если где-то хеш стал отрицательным - все пропало.

[Никита]

Увеличил размер строки и образа - хэш стал отрицательным. В массиве степеней переполнение: значения становятся отрицательными, хэш умножается на отрицательное число и тоже становится отрицательным. Пробовал взять long long, но это не помогает. Что делать в этом случае? Степени ведь нужно как-то хранить.

[Wataru]

Никита, Надо хеш везде считать по модулю. Можно считать по модулю 2^32 - для этого все переменные и константы в вычислении хеша должны быть unsigned int. Там тоже будет переполнение, но оно безобидное и будет как будто вы берете все по модулю 2^32.

[Никита]

Изменил int на unsigned int. Все та же ошибка - Ошибка времени исполнения.

Описание ошибки

Ошибка времени исполнения ваш код выполнил что-то противозаконное:
вылез за границы массива (самый часто встречающийся случай (если вы пишете на C или C++, то на вашем компьютере все может работать и вы даже не поймете, что на самом деле все плохо));
поделил на ноль;
взял корень из отрицательного числа;
обратился к уже удаленному из памяти элементу;
все что угодно, что непонятно как должно работать;

Является ли переполнение такого рода ошибкой?

[Wataru]

Никита, Попробуйте скормить тест, где шаблон длиннее текста. Попробуйте ввести шаблон из одного символа.

[Никита]

Wataru, Не заметил, что создается массив на n - m элементов. Исправил, но теперь по времени не проходит. Не подскажите, как можно ускорить время работы?

[Wataru]

Никита, Ваш алгоритм на тесте из всех букв "a" будет работать за n*m.

Можно попробовать не проверять equals и надеятся, что у вас достаточно хороший хеш. Но может не повезти. Если будут неправильные ответы, то можно будет попробовать поменять X, или еще лучше добавить хешей, с другим значением X и проверять на равенство все хеши.

Еще, я бы посоветовал реализовать другой алгоритм поиска подстроки, например КМП или Бойера-Мура.

[Никита]

Wataru, Спасибо за помощь) Попробую через КМП. Изначально пробовал Бойера-Мура, но превышение по времени на том же тесте