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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Jeorge
Сообщений: n/a
#1

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

18.05.2011, 16:02. Просмотров 418. Ответов 0
Метки нет (Все метки)

Задача: поиск подстроки в строке с помощью алгоритма Хорспула. Строка задаётся из 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++
алгоритм accumulate C++
C++ Алгоритм поиска
C++ алгоритм RLE
C++ Алгоритм Тасовки
C++ Создать алгоритм
Алгоритм STL C++
C++ Рекурсивный алгоритм
Реализовать алгоритм C++
C++ Алгоритм с Паскаля на С++
Объясните алгоритм C++

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

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

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