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

Очень прошу разъяснить код алгоритма Бойера-Мура - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ вывод результатов http://www.cyberforum.ru/cpp-beginners/thread591758.html
#include <iostream> #include <math.h> #include<conio.h> #include <stdlib.h> const int n = 10; void fill( float *a ) { std::srand( std::time( 0 ) );
C++ Прототип функции чтения динамического списка из файла Всем доброго времени суток. У кого нибудь есть прототип функции чтения динамического списка из файла? http://www.cyberforum.ru/cpp-beginners/thread591746.html
C++ Вывести окружность с максимальным количеством точек внутри окружности
Уважаемые программисты , очень хочу попросить у вас помощи в написание одной программы! мне дали задание ,которое я совсем не могу написать. поэтому прошу помощи у вас, и надеюсь на вашу помощь!! задание : Вывести окружность с max количеством точек(произвольно расположенных) внутри , которая проходит через 3 точки! к примеру N точек = 100, окружность радиусом R=10!. да и окружность должна...
Синтаксический анализатор C++
Нужно написать синтаксический анализатор для одного маленького фрагмента программы, т.е. проверка правильности грамматического построения предложений исходного текста программы. Текст программы: if (CEdit1.Text='') and (Kedit2.Text='') then begin ShowMessage('Please enter data');exit end; Это должно быть просто окно, куда я вставляю код и при нажатии кнопки либо выдаётся сообщение что...
C++ Обмен данными между программами http://www.cyberforum.ru/cpp-beginners/thread591732.html
Я в С++ не силён , но интерес есть , не могу найти в интернете по С++ чтобы две программы обменивались данными по протоколу http:80 . Как набрать в поиске ? по делфи нашел , а по с++ NULL false
C++ Вычисления количества простых чисел, принадлежащих отрезку Задание: Составить программу вычисления количества простых чисел, принадлежащих отрезку . Для проверки, является ли число простым, использовать функцию prostoe. Функция возвращает 1, если число является простым, а 0 - в противном случае. / / Функция проверяет, является ли число простым int prostoe (int n) {Int d, r; d = 2; do { r = n% d; if (r! = 0) d + +; } while (r! = 0); / / пока n не... подробнее

Показать сообщение отдельно
THE HOST
Сообщений: n/a

Очень прошу разъяснить код алгоритма Бойера-Мура - C++

30.05.2012, 20:40. Просмотров 2495. Ответов 1
Метки (Все метки)

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
#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;
 }
}
 
char *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 string+i+1;
  }
  i += max(delta1[string[i]], delta2[j]);
 }
 delete delta2;
 return NULL;
}
 
int main()
 {
 char *string="This is a test string for my test program";
 char *pattern="test";
 cout << "Result=" << boyer_moore(string,pattern) << endl;   
 system("PAUSE");
 return EXIT_SUCCESS;
}
Помогите, пожалуйста, разобраться!!! Мне нужно защитить этот код, но я не могу разобрать некоторые строки!
C++
1
#define max(a, b) ((a < b) ? b : a)
- для чего нужна эта строка? //я понимаю, что это условная операция, но какую роль она выполняет в коде?
int suffixlen = wordlen - pos;- что обозначает эта строка?
C++
1
 i += max(delta1[string[i]], delta2[j]);
- что делает эта строка?
C++
1
int *delta2 = new int [patlen * sizeof(int)]
- и вот эта строка?
P.S. да, я совсем ничего не понимаю в С++!
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru