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

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

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

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

17.12.2011, 12:34. Просмотров 3583. Ответов 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 минут
Что за времена нынче пошли. Раньше обращались на форум и хоть как то помогали. может время другое настало? или модераторы сменились?
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Alligieri
17.12.2011, 12:50
  #2

Не по теме:

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

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

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

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

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

Добавлено через 2 часа 42 минуты
хоть кто нибудь может подсказать что знает по этому коду?
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
20.12.2011, 16:51     Алгоритм Рабина-Карпа, нужны комментарии к коду
Еще ссылки по теме:
Реализация алгоритма Рабина-Карпа для двух однонаправленных линейных списков C++
C++ (ищу алгоритм) Хопкрофта-Карпа
Алгоритм шифрования Рабина C++
Комментарии к коду C++
Комментарии к коду C++

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

Или воспользуйтесь поиском по форуму:
_масяня_
28 / 28 / 2
Регистрация: 18.12.2010
Сообщений: 158
20.12.2011, 16:51  [ТС]     Алгоритм Рабина-Карпа, нужны комментарии к коду #9
так и не нашлоось сдесь настоящих профессионалов, которые могут помочь((((
Yandex
Объявления
20.12.2011, 16:51     Алгоритм Рабина-Карпа, нужны комментарии к коду
Ответ Создать тему
Опции темы

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