Форум программистов, компьютерный форум CyberForum.ru

Алгоритм Хоспула - C++

Восстановить пароль Регистрация
 
Jeorge
Сообщений: n/a
18.05.2011, 16:02     Алгоритм Хоспула #1
Задача: поиск подстроки в строке с помощью алгоритма Хорспула. Строка задаётся из 10 млн случайных символов. Подстрока состоит, например, из 1 млн символов.
А проблема в том, что алгоритм Хорспула ни в какую не хочет работать при случайном наборе строк. Но работает нормально, если строки вручную вводишь. Может кто подскажет в чём проблема?
Код
#include <iostream>
#include <string>
using namespace std;

int HorspoolMatch(string T,string P)
{	
	int n=T.length();
	int m=P.length();
	int Slide[256];
	for(int i=0; i<256; ++i)
		Slide[i]=m;
	for(int l=0; l<m; ++l)
		Slide[P[l]] = m - l - 1;

	int k=0;
	while(k < n - m + 1)
	{
		for(int i=0; i<m; i++)
		{
			if(T[k+i]!=P[i])
				break;
			if(i==m-1)
				return k;
		}
		k += Slide[T[k+m-1]];
	}
	return -1;
}

void main()
{
	setlocale (LC_ALL, "Russian");
	
	string T="";//строка, в которой ищем
	string P="";//строка, которую ищем
	string S="";//строка,для создания случайных символов,которые добавляются потом в строки T и P
	//генерируем строки
	for(int i=0; i<1000000;i++)
	{
		S=rand();
		T.append(S);
		if(i>1 && i<5)
		{
			P.append(S);
		}
	}

	cout << "Алгоритм Хорспула: " << HorspoolMatch(T,P) <<  endl;
	
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
18.05.2011, 16:02     Алгоритм Хоспула
Посмотрите здесь:

C++ Алгоритм
C++ c++/алгоритм
алгоритм C++
алгоритм C++
C++ Алгоритм
Алгоритм C++
C++ Алгоритм А*
C++ алгоритм бм

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

Текущее время: 05:35. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru