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

как работает эта программа(Алгоритм Рабина-Карпа с++)??? - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 25, средняя оценка - 4.68
_масяня_
 Аватар для _масяня_
28 / 28 / 2
Регистрация: 18.12.2010
Сообщений: 158
17.12.2011, 12:34     как работает эта программа(Алгоритм Рабина-Карпа с++)??? #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
/* Рабина-Карпа строку алгоритме сопоставления
  - Предположим, Т и Р состоит только а до я и А. 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 минут
Что за времена нынче пошли. Раньше обращались на форум и хоть как то помогали. может время другое настало? или модераторы сменились?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
17.12.2011, 12:34     как работает эта программа(Алгоритм Рабина-Карпа с++)???
Посмотрите здесь:

C++ (ищу алгоритм) Хопкрофта-Карпа
Алгоритм шифрования Рабина C++
Реализация алгоритма Рабина-Карпа для двух однонаправленных линейных списков C++
C++ Как работает эта функция?
Как работает эта часть кода? C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Alligieri
17.12.2011, 12:50
  #2

Не по теме:

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

_масяня_
 Аватар для _масяня_
28 / 28 / 2
Регистрация: 18.12.2010
Сообщений: 158
17.12.2011, 18:58  [ТС]     как работает эта программа(Алгоритм Рабина-Карпа с++)??? #3
мне очень нужна помощь, Alligieri можете мне помочь закоментировать этот код? это очень важно. шарю в с++ я еще плохо, если можете то помогите пожалйста
Даня98
 Аватар для Даня98
27 / 27 / 8
Регистрация: 13.02.2010
Сообщений: 145
17.12.2011, 19:02     как работает эта программа(Алгоритм Рабина-Карпа с++)??? #4
вам нужен именно этот код?
Dani
1263 / 621 / 50
Регистрация: 11.08.2011
Сообщений: 2,236
Записей в блоге: 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
1263 / 621 / 50
Регистрация: 11.08.2011
Сообщений: 2,236
Записей в блоге: 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++ Как работает эта программа? (клиент-сервер)

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

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

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