Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > C/C++ программирование > Общие вопросы C/C++
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 03.11.2014, 12:51   #1
KatyaKatch
Новичок
Джуниор
 
Регистрация: 03.11.2014
Сообщений: 1
По умолчанию алгоритм Бойлера-Мура

Мой алгоритм находит позицию первого вхождения. Пыталась исправить. пока не получилось. Помогите сделать так, чтобы алгоритм выводил позиции всех вхождений
Код:
#include <cstdlib>
#include <iostream>
#include <string>

#define ALPHABET_LEN 255 
#define NOT_FOUND patlen 
#define max(a, b) ((a < b) ? b : a)

using namespace std;

void make_delta1 (int *delta1, char *pat, long int patlen)
{
	int i;
	for (i=0; i < ALPHABET_LEN; i++) delta1[i] = NOT_FOUND;
	for (i=0; i < patlen-1; i++) delta1[pat[i]] = patlen-1-i;
}

int is_prefix (char *word, int wordlen, int pos) 
{
	int suffixlen = wordlen - pos;
	for (int i = 0; i<suffixlen; i++) 
	{
		if (word[i] != word[pos+i]) return 0;
	}
	return 1;
}
int suffix_length (char *word, int wordlen, int pos)
{
	int i;
	for (i = 0; (word[pos-i] == word[wordlen-1-i]) && (i < pos); i++);
	return i;
}

void make_delta2(int *delta2, char *pat, long int patlen)
{
	int last_prefix_index = patlen-1;
	int p;
	for (p=patlen-1; p>=0; p--) 
	{
		if (is_prefix(pat, patlen, p+1)) last_prefix_index = p+1;
		delta2[p] = last_prefix_index + (patlen-1 - p);
	}
	for (p=0; p < patlen-1; p++)
	{
		int slen = suffix_length(pat, patlen, p);
		if (pat[p-slen]!=pat[patlen-1-slen]) delta2[patlen-1-slen]=patlen-1-p+slen;
	}
}

int boyer_moore (char *string, char *pat) 
{
	long int stringlen = strlen(string);
	long int patlen =strlen(pat);
	int delta1[ALPHABET_LEN];
	make_delta1(delta1, pat, patlen);
	int *delta2 = new int [patlen * sizeof(int)];
	make_delta2(delta2, pat, patlen);
	int i = patlen-1;
	while (i < stringlen)
	{
		int j = patlen-1;
		while (j >= 0 && (string[i] == pat[j])) 
		{
			--i; --j;
		}
		if (j < 0) 
		{
			delete delta2;
			return i+2;
			int k=i+2;
			for (int f=0;f<=k+1;f++)
			string[f]=0;
			
		}
		i += max(delta1[string[i]], delta2[j]);
		
	}

	delete delta2;
	return NULL;
}

int main()
{
	char *string="ceea babc";
	char *pattern="a";
	long int stringlen = strlen(string);
	for (int l=0;l<stringlen;l++)
	{
		cout << boyer_moore(string,pattern)<<" "<<endl;  
	}
	return EXIT_SUCCESS;
}

Последний раз редактировалось ACE Valery; 03.11.2014 в 18:38.
KatyaKatch вне форума Ответить с цитированием
Старый 03.11.2014, 15:32   #2
min@y™
Цифровой кот
Старожил
 
Аватар для min@y™
 
Регистрация: 29.08.2014
Сообщений: 7,656
По умолчанию

Сюда читай.
Расскажу я вам, дружочки, как выращивать грибочки: нужно в поле утром рано сдвинуть два куска урана...
min@y™ вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Разработайте алгоритм методом пошаговой детализации и программу, реализующую этот алгоритм. iamhated Помощь студентам 1 15.01.2012 16:24
Разработайте алгоритм методом пошаговой детализации и программу, реализующую этот алгоритм iamhated Помощь студентам 1 14.01.2012 16:22
Алгоритм TMDS (Алгоритм передачи данных интерфейса DVI) Pro4RE Помощь студентам 2 24.04.2011 21:55
Автоматы Бойера- Мура killer12rus Помощь студентам 1 21.12.2010 20:55
Просьба помочь разобраться с поиском в строке по алгоритму Бойера-Мура Ветас Помощь студентам 1 16.11.2009 18:52