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

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

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Строки/Матрицы/Функции/Списки http://www.cyberforum.ru/cpp-beginners/thread409395.html
Доброго времени суток! Очень нуждаюсь в помощи, срочно. Нужно написать 4 проги, вроде лёгкие, но я сам не могу понять :( 1) Строки: Дана строка: Ваши фамилия, имя и отчество записаны через один пробел. Подсчитать кол - во букв "о" во всей строке. 2) Матрицы:Дана матрица. Найти для каждой строки матрицы сумму максимального и минимального элементов. Распечатать в виде столбца. 3) Функции:...
C++ Удалить каждое четное слово из строки Задача: Удалить каждое четное слово из строки. Это то что надо получить в конце, но т.к. я пытаюсь разобраться, хотелось бы по подробнее шаги рассмотреть! Идею задачи я понимаю. Но сразу же столкнулся с проблемой написания кода...(подсчет количества слов в введенной строке) #include <iostream> #include <cstring> #include <Windows.h> using namespace std; void main() http://www.cyberforum.ru/cpp-beginners/thread409394.html
остаток от деления C++
обычно использовал "%" для отделения остатка от деления двух чисел только для того чтобы узнать целочисленное деление или нет. Теперь когда надо найти элементом с остатком от деления на три равный 2 не получается. if((a%3)==2) проверял к примеру 12%8 выдает 4 хотя должно быть 5. в чем ошибка. Я уже подумывал что оператор "%" используется только для определения целочисленого деления? ...
Вводить с клавиатуры числа до тех пор, пока не будет нажата клавиша <<ESC>> C++
Задание: Вводить с клавиатуры числа до тех пор, пока не будет нажата клавиша <<ESC>>. На экран вывести кол-во вводимых чисел. #include <string> #include <iostream> #include <conio.h> using namespace std; int main() { int ch; int i;
C++ Борьба за ресурсы http://www.cyberforum.ru/cpp-beginners/thread409383.html
Добрый день! Встал вопрос, возможно надуманный. void* a(void* argv) { while(1) { cout << (char*)argv; } } void* b(void* argv)
C++ "Аномалия" в сортировке массивов Есть массив чисел int. В котором присутствуют как отрицательные, так и положительные числа. Есть два цикла for - один из которых записывает все отрицательный числа в конец массива, другой в начало, на вид они одинаковы, почему по разному работают? Вот код первого (отрицательный числа в конец) int num = { -1,-2,3,4,-1,6,-7,8, -1, -1 }; for(int y=0; y<10-1; y++){ for(int f=0;... подробнее

Показать сообщение отдельно
_масяня_
28 / 28 / 2
Регистрация: 18.12.2010
Сообщений: 158

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

17.12.2011, 12:34. Просмотров 3569. Ответов 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 минут
Что за времена нынче пошли. Раньше обращались на форум и хоть как то помогали. может время другое настало? или модераторы сменились?
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru