@Nikitos2002

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

Написал полиномиальную хэш-функцию без взятия остатка, может ли быть ошибка в этом? Алгоритм не проходит второй тест.
Задача:
Даны строки 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;
}
  • Вопрос задан
  • 106 просмотров
Решения вопроса 1
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, экс-олимпиадник.
Возможно там переполнение. Убедитесь, что у вас все хеши везде считаются только с участием unsigned типов. Переполнение в signed - это Undefined behavior.
Ответ написан
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы