Форум программистов, компьютерный форум, киберфорум
Наши страницы

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

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

Выдает ошибки: поиск по шаблону, Бойер-Мур и Рабин-Карп. - C++

02.06.2011, 18:50. Просмотров 805. Ответов 0
Метки нет (Все метки)

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
#include <stdio.h>
#include <conio.h>
#include <string.h>
#include <limits.h>
#define EOS '\0'
#define REHASH( a, b, h ) ((( h - a * d ) << 1 ) + b )
 
using namespace std;
 
int main(int argc, char *argv[])
{
    /* Алгоритм Бойера-Мура */
 
int Pos;
static int suffix_match(const unsigned char *needle, size_t nlen, size_t offset, size_t suffixlen)
 {
 if (offset > suffixlen)
 return needle[offset - suffixlen - 1] != needle[nlen - suffixlen - 1] &&
 memcmp(needle + nlen - suffixlen, needle + offset - suffixlen, suffixlen) == 0;
 else
 return memcmp(needle + nlen - offset, needle, offset) == 0;
 }
 
 static size_t max(size_t a, size_t b)
 {
 return a > b ? a : b;
 }
 
 const unsigned char* memmem_boyermoore
 (const unsigned char* haystack, size_t hlen,
 const unsigned char* needle, size_t nlen)
 {
 size_t skip[UCHAR_MAX+1]; 
size_t occ[UCHAR_MAX+1]; 
 size_t a;
 if(nlen > hlen || nlen <= 0 || !haystack || !needle)
 return NULL;
 
 for(a=0; a<nlen; ++a)
 occ[a] = -1;
 
 for(a = 0; a < nlen - 1; ++a)
 occ[needle[a]] = a;
 
for(a = 0; a < UCHAR_MAX+1; ++a)
 {
 size_t offs = nlen;
 while(offs && !suffix_match(needle, nlen, offs, a))
 --offs;
 skip[nlen - a - 1] = nlen - offs;
 }
 
for(size_t hpos = 0; hpos <= hlen - nlen; )
 {
 size_t npos = nlen - 1;
 
 while(needle[npos] == haystack[npos + hpos])
 {
 if(npos == 0)
 return haystack + hpos;
 
 --npos;
 }
hpos += max(skip[npos], npos - occ[haystack[npos + hpos]]);
 
 }
 return NULL;
 }
 
 
/* Алгоритм Рабина-Карпа*/
 
 
void KR( char *y, char *x, int n, int m ) {
 int hy, hx, d, i;
  d = 1;
  for ( i = 1; i < m; i++ ) d = ( d << 1 );
  hy = hx = 0;
  for ( i = 0; i < m; i++) {
      hx = ( ( hx << 1 ) + x[i] );
     hy = ( ( hy << 1 ) + y[i] );
   }
   for ( i=m; i < n; i++ ) {
      if ( hy == hx && memcmp( &y[ i-m-1 ], x, m ) == 0 ) //OUTPUT( i-m );
     hy = REHASH( y[i-m], y[i], hy );
    }
  }
void main(){
char s[]="mama mila ramu\0";
char x[]="mila ramu";
char result[80];
int n=15;
int m=9;
clrscr();
Pos=-1;
Cout<<"source string:"<<s<<enld;
Cout<<"looking:"<<x<<endl;
BF(x,s,m);
if (memmem_boyermoore(s,n,x,m)!=NULL) cout<<"Algorithm Boyer-Moore substring found"<<endl;
else cout<<" Algorithm Boyer-Moore substring not found"<<endl;
Pos=-1;
KR(x,s,m,n);
if (Pos==-1) cout<<"Algorithm Karp-Rabin substring not found"<<endl;
else cout<<" Algorithm Karp-Rabin substring is found at position"<<Pos<<endl;
 
    system("PAUSE");
    return EXIT_SUCCESS;
}
 Комментарий модератора 
Используйте теги форматирования кода!
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
02.06.2011, 18:50
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Выдает ошибки: поиск по шаблону, Бойер-Мур и Рабин-Карп. (C++):

Не получается реализовать поиск подстроки в строке. Бойер-Мур - C++
Нужно чтобы выводило количество совпадений каждым алгоритмом. Получился Боера-Мура считает не всегда правильно. Линейный алгоритм всё...

Боуер Мур. поиск подстроки - C++
Написал код, но он некорректно ищет подстроку. В зависимости где находится искомый элемент в тексте. Может вы найдете ошибку? #include...

Поиск по шаблону * и? - C++
Здраствуите можете помочь с малеьким таки заданием ,я пытался еа куралесить ну не получилось. я вложил исходник в текстовом фаиле

Поиск по шаблону - C++
При реализации поиска по шаблону столкнулся со следующей проблемой: Шаблон: *abc Тест1: abc Тест2: fabc Тест3: ssabk_abc Первые...

[OpenCV] Поиск по шаблону - C++
Добрый день, имеется код с robocraft, в котором используется функция cvMatchTemplate, вопрос состоит в том, чтобы узнать нашла ли функция...

Рабин-карп - Turbo Pascal
Ребят,есть алгоритм Рабина-Карпа.Разобрал все,кроме функции ReHash.Может кто может объяснить для чего она тут?Вот сам алгоритм: ...

0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
02.06.2011, 18:50
Привет! Вот еще темы с ответами:

Поиск из поля text1 выдает ошибки - FoxPro
Здравствуйте. Помогите пожалуйста с кодом. Суть в том, чтоб в форме, в поле text1 пользователь писал код товара(поле типа integer) и в...

QRegExp поиск всех строк которые соответствуют шаблону и поиск их длины - C++ Qt
//поиск строк типа ] QRegExp reg(&quot;\\\\]&quot;); QString text = &quot;test ] bla ]&quot;; int pos = reg.indexIn(text); //здесь ошибка....

Поиск в текстовом файле последовательностей цифр по шаблону и последующий их поиск в именах файлов (с логом) - CMD/BAT
Уважаемые программисты и хорошие люди! К Вам обращается украинский юрист. Очень нужен bat-файл или скрипт, который решает такую задачу: ...

Поиск в текстовых файлах символьных групп по шаблону и последующий поиск найденных в именах файлов (с логом) - PowerShell
Господа программисты! Прошу помочь в таком вопросе! Исходные данные: Последовательности такого вида: где ???? - это...


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

Или воспользуйтесь поиском по форуму:
1
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.