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

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 18, средняя оценка - 4.67
THE HOST
Сообщений: n/a
30.05.2012, 20:40     Очень прошу разъяснить код алгоритма Бойера-Мура #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. да, я совсем ничего не понимаю в С++!
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
30.05.2012, 20:40     Очень прошу разъяснить код алгоритма Бойера-Мура
Посмотрите здесь:

C++ Алгоритм Бойера-Мура
C++ Ошибка в функции поиска подстроки в строке. Алгоритм Бойера-Мура-Хорспула.
C++ Поиск подстроки в строке(алгоритм Бойера-Мура)
C++ Я не прошу писать мне код, я прошу подсказать мне, что за структура требуется в задании
C++ Прошу объяснить о ссылках,указателях,стрелке -> и двоеточиях :: очень прошу я не понял синтаксис
C++ Имеется код программы, выводящий список автобусов из файла, нужно разъяснить его
Алгоритм Бойера и Мура C++
C++ Алгоритм Бойера-Мура поиска подстроки в строке (Js -> C++)

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
instagib
122 / 85 / 3
Регистрация: 14.02.2011
Сообщений: 341
30.05.2012, 20:46     Очень прошу разъяснить код алгоритма Бойера-Мура #2
Цитата Сообщение от THE HOST Посмотреть сообщение
#define max(a, b) ((a < b) ? b : a)
макрос возвращает максимальное из двух значений.
Цитата Сообщение от THE HOST Посмотреть сообщение
int suffixlen = wordlen - pos;- что обозначает эта строка?
новой переменной suffixlen присваивается разность worldlen и pos
Цитата Сообщение от THE HOST Посмотреть сообщение
i += max(delta1[string[i]], delta2[j]); - что делает эта строка?
к переменной i прибавляется максимальное из элементов массивов.
Цитата Сообщение от THE HOST Посмотреть сообщение
int *delta2 = new int [patlen * sizeof(int)] - и вот эта строка?
новому указателю выделяется динамическая память размером patlen умноженным на размер целого числа

Добавлено через 1 минуту
THE HOST,

Не по теме:

оформляйте код в соответствующие теги форматирования.

Yandex
Объявления
30.05.2012, 20:46     Очень прошу разъяснить код алгоритма Бойера-Мура
Ответ Создать тему
Опции темы

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