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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 25, средняя оценка - 4.68
_масяня_
28 / 28 / 2
Регистрация: 18.12.2010
Сообщений: 158
#1

Алгоритм Рабина-Карпа, нужны комментарии к коду - C++

17.12.2011, 12:34. Просмотров 3674. Ответов 8
Метки нет (Все метки)

Привет всем. Столкнулся с задачей разобраться с кодом алгоритма рабина карпа. Объясните пожалуйста как в данной программе он работает.
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
/* Рабина-Карпа строку алгоритме сопоставления
  - Предположим, Т и Р состоит только а до я и А. Z..
  - проверка является ли P подстрокой Т
  - Вернуть начальный индекс первого вхождения P в T
  - m = длина (Т)
  - n = длина (Р)
      Худший случай: ((п-т +1) * м)
      Лучший случай: (п + т)
*/
//---------------------------------------------------------------------------
#define tonum(c) (c >= 'A' && c <= 'Z' ? c - 'A' : c - 'a' + 26)
 
  /* return a^p mod m */
  int mod(int a,int p,int m)
  {
       if (p == 0) return 1;
       int sqr = mod(a,p/2,m) % m;
       sqr = (sqr * sqr) % m;
       if (p & 1) return ((a % m) * sqr) % m;
       else return sqr;
  }
 
  int RabinKarpMatch(char *T,char *P,int d,int q)
  {
       int i,j,p,t,n,m,h,found;
       n = strlen(T);
       m = strlen(P);
       h = mod(d,m-1,q);
       p = t = 0;
 
   for (i=0; i<m; i++)
       {
            p = (d*p + tonum(P[i])) % q;
            t = (d*t + tonum(T[i])) % q;
       }
 
   for (i=0; i<=n; i++)
       {
            if (p == t)
            {
                 found = 1;
                 for (j=0; j<m; j++)
                     if (P[j] != T[i+j])
                     {
                         found = 0;
                         break;
                     }
                 if (found) return i+1;
            } else {
                 t = (d*(t - ((tonum(T[i])*h) % q)) + tonum(T[i+m])) % q;
            }
       }
       return -1;
  }
#pragma argsused
int main(int argc, char* argv[])
{     int sovp;
      int d=1, q=1;
      char *T="Kachdii den iya vstay na yaseby";
      char *P="den";
      cout<<"             Algoritm Rabina-Karpa\n"<<"\n----------------------------------\n";
      cout<<"Kachdii den iya vstay na yseby i idy v BGTY\n\n";
      cout<<"Find-->den\n\n";
      sovp= RabinKarpMatch(T,P,d, q);
      if(sovp)
      cout<<"Slovo naideno v "<<sovp<<" posizii";
      else
      cout<<"Sovpadenii ne naideno!!!";
      getch();
      return 0;
}
//------------------------------------
Добавлено через 1 час 19 минут
неужели здесь нет профессионалов чтобы расшифровать такой кусочек кода?

Добавлено через 12 минут
ау? помогите кто нибудь

Добавлено через 17 минут
мне хотя бы по строчкам прокоментировать, что в каждой строчке происходит

Добавлено через 10 часов 45 минут
Что за времена нынче пошли. Раньше обращались на форум и хоть как то помогали. может время другое настало? или модераторы сменились?
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
17.12.2011, 12:34
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Алгоритм Рабина-Карпа, нужны комментарии к коду (C++):

Алгоритм Рабина-Карпа - C++
Всем доброго времени суток! Имеется код Алгоритма Рабина-Карпа, поиск подстроки в строке. Сегодня сдавать, боюсь сам полностью не...

Усовершенствовать алгоритм Рабина-Карпа, чтобы он искал символьную подматрицу в символьной матрице - C++
У меня есть этот алгоритм. Кто знает, как усовершенствовать его, чтобы он искал символьную подматрицу m * m в символьной матрицы n * n, при...

Нужны комментарии к коду - C++
pair&lt;bool, array&lt;int, 81&gt;&gt; SOL(const char* inp) { array&lt;int, 81&gt; ANS; int* TAB = ANS.data(); int emp; int c = 0; int i, j,...

Нужны комментарии к коду - C++
#include &lt;iostream&gt; #include &lt;cmath&gt; using namespace std; //ЗАДАЧА #14 void print_array(int *a, int n) { for (int...

Нужны комментарии к коду - C++
int bestStr(char** file, int numstr) { int iBest = -1, bestwords = 0; for (int i = 0; i &lt; numstr; i++) { int goodwords =...

Список (нужны комментарии к коду) - C++
вот код на cpp обьясните плиз последние 5 строк.и this. template &lt;class genius1&gt; class List_Elem { friend class List &lt;genius1&gt;; ...

8
Alligieri
17.12.2011, 12:50
  #2

Не по теме:

_масяня_, суббота, утро, выходной... вы думаете людям делать нечего только комментировтаь этот неясный кусок кода?!

0
_масяня_
28 / 28 / 2
Регистрация: 18.12.2010
Сообщений: 158
17.12.2011, 18:58  [ТС] #3
мне очень нужна помощь, Alligieri можете мне помочь закоментировать этот код? это очень важно. шарю в с++ я еще плохо, если можете то помогите пожалйста
0
Даня98
28 / 28 / 8
Регистрация: 13.02.2010
Сообщений: 145
17.12.2011, 19:02 #4
вам нужен именно этот код?
0
Dani
1393 / 637 / 57
Регистрация: 11.08.2011
Сообщений: 2,283
Записей в блоге: 2
Завершенные тесты: 1
17.12.2011, 19:04 #5
Цитата Сообщение от Даня98 Посмотреть сообщение
вам нужен именно этот код?
если нет, то вот
1
_масяня_
28 / 28 / 2
Регистрация: 18.12.2010
Сообщений: 158
17.12.2011, 19:11  [ТС] #6
да. я нашел этот алгоритм- вроде как правильно работает. остается только понять как он ищет подстроку в строке исходя из данного кода. Даня98 есть другой код алгоритма Рабина-Карпа? закоменченый?

Добавлено через 1 минуту
Dani спасибо, но мне нужен именно этот)) все равно большое спасибо)

Добавлено через 4 минуты
мне бы мой код закоментить как нибудь, а то совсем не понятно как он работает
1
Dani
1393 / 637 / 57
Регистрация: 11.08.2011
Сообщений: 2,283
Записей в блоге: 2
Завершенные тесты: 1
17.12.2011, 19:14 #7
Предупреждаю! Следующий тескт стырен где-то
Идея, предложенная Рабином и Карпом, подразумевает ставить в соответствие каждой строке некоторое уникальное число, и вместо того, чтобы сравнивать сами строки, сравнивать числа, что намного быстрее. Проблема в том, что искомая строка может быть длинной, строк в тексте тоже нехватает. А так как каждой строке нужно сопоставить уникальное число, то и чисел должно быть много, а стало быть - числа будут большими.

Добавлено через 1 минуту
Во...
Призводить все арифмитические действия, по модулю какого-то простого числа (постоянной брать остаток от деления на это число).
1
_масяня_
28 / 28 / 2
Регистрация: 18.12.2010
Сообщений: 158
17.12.2011, 21:59  [ТС] #8
Dani, как он работает по сути я знаю. а вот как он работает по этому коду- это большой вопрос. Мне нужно преподавателю обьяснить что делает это программа в каждой строчке кода. Кто может объясните пожалуйста

Добавлено через 2 часа 42 минуты
хоть кто нибудь может подсказать что знает по этому коду?
1
_масяня_
28 / 28 / 2
Регистрация: 18.12.2010
Сообщений: 158
20.12.2011, 16:51  [ТС] #9
так и не нашлоось сдесь настоящих профессионалов, которые могут помочь((((
0
20.12.2011, 16:51
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
20.12.2011, 16:51
Привет! Вот еще темы с ответами:

Нужны комментарии к коду с указателями - C++
Добавить комментарии к коду так, что бы можно было понять что и как используется. #include &lt;iostream&gt; #include &lt;cmath&gt; #include...

Сортировка массива (нужны комментарии к коду) - C++
Объясните пожалуйста, что значит каждый рядок 1 #include &lt;iostream&gt; void compare(int arr,int size) { for(int i = 0; i...

Контейнер map (нужны комментарии к коду) - C++
Может кто прокомментировать строки? Не могу разобрать, что делает программа. Буду благодарен ) #include &lt;iostream&gt; #include &lt;map&gt; ...

Реализация алгоритма Рабина-Карпа для двух однонаправленных линейных списков - C++
Здравствуйте! Собственно, вопрос находится в заголовке: у меня описано два списка, надо этим алгоритмом найти количество вхождений первого...


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

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

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