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

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

Войти
Регистрация
Восстановить пароль
 
Krooxe
Сообщений: n/a
#1

Помогите доделать алгоритм Бойера-Мура-Хорспула - C++

24.06.2014, 00:09. Просмотров 459. Ответов 0
Метки нет (Все метки)

помогите, пожалуйста, реализовать алгоритм Краскала для смежных матриц. Вот с другом как-то пытались, но нам кажется, что получился какой-то бред

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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
#ifndef CSUB_H
#define CSUB_H
 
int BoyerMooreHorspool2(std::string &haystack, std::string &needle)
{       
    int i, j, k;
    int needle_len = 0; //длина строки, в которой осуществляется поиск      
    int haystack_len = 0; //длина нашего шаблона
    int needle_table[256]; // таблица символов
 
    // подсчет кол-ва символов в needle
    needle_len = needle.size();
    // подсчет кол-ва символов в haystack
    haystack_len = haystack.size();
 
    if (needle_len < haystack_len)  
    {
        for (i = 0; i < 256; i++) // в таблицу заносится для каждого символа длина needle
            needle_table[i] = needle_len; 
 
        for (i = 1; i < needle_len; i++) // каждому символу из таблицы ставиться в соответствие его порядковый номер из needle, т.е таблица смещений
            needle_table[needle[i-1]] = needle_len-i; 
 
        i = needle_len; // i - счетчик текущего последнего символа в haystack 
        j = i; // j - счетчик в needle кол-ва одинаковых символов (совпадающих с таблицей) с конца 
 
        while (j > 0 && i <= haystack_len) // если j==0 то совпадение найдено
        {
            j = needle_len; // заново выполняем присваивание, чтобы сравнивать строки с конца
            k = i; // k - счетчик текущего символа в haystack
                   // j - счетчик текущего символа в needle
            
            while (j > 0 && haystack[k-1] == needle[j-1]) // сравнение последних симолов
            { // если равны, то сравниваем предыдущие
                //comp++;
                --k;
                --j;                    
            }
                    
            i += needle_table[haystack[i-1]]; // сдвигаем шаблон на следующий совпадающий символ из таблицы и haystack
                        // т.е. в needle ищется (т.е. уже дан в таблице) последний сравниваемый символ из haystack
        }
 
        if (k > haystack_len - needle_len) // если k выходит за пределы сравнения
            return 0;
        else return k + 1; // иначе k == текущая позиция подстроки needle в строке haystack 
                // k показывает смещение в haystack, предполагая, что строка начинается с 1 
    }
    else return 0;  
}
 
/*
int BoyerMooreHorspool(char *haystack, char *needle)
{       
    int comp;
    int i, j, k;
    int needle_len = 0; //длина строки, в которой осуществляется поиск
    int haystack_len = 0; //длина нашего шаблона
    int needle_table[256]; // таблица стоп-символов
 
    // char *ch - указатель на символ
    for (char *ch = needle; *ch; *ch++) // подсчет кол-ва символов в needle
        ++needle_len;
    for (char *ch = haystack; *ch; *ch++) // подсчет кол-ва символов в haystack
        ++haystack_len;
    
    if (needle_len < haystack_len)  
    {
        for (i = 0; i < 256; i++) // в таблицу заносится для каждого символа длина needle
            needle_table[i] = needle_len; 
        
        for (i = 1; i < needle_len; i++) // каждому символу из таблицы ставиться в соответствие его порядковый номер из needle, т.е таблица смещений
            needle_table[needle[i-1]] = needle_len-i; 
 
            i = needle_len; // i - счетчик текущего последнего символа в haystack 
            j = i; // j - счетчик в needle кол-ва одинаковых символов (совпадающих с таблицей) с конца 
 
            while (j > 0 && i <= haystack_len) // если j==0 то совпадение найдено
            {
                j = needle_len; // заново выполняем присваивание, чтобы сравнивать строки с конца
                k = i; // k - счетчик текущего символа в haystack
                               // j - счетчик текущего символа в needle
                comp++;
                while (j > 0 && haystack[k-1] == needle[j-1]) // сравнение последних симолов
                { // если равны, то сравниваем предыдущие
                    --k;
                    --j;
                    comp++;
                 }
                 i += needle_table[haystack[i-1]]; // сдвигаем шаблон на следующий совпадающий символ из таблицы и haystack
                 // т.е. в needle ищется (т.е. уже дан в таблице) последний сравниваемый символ из haystack
             }
            if (k > haystack_len - needle_len) // если k выходит за пределы сравнения
                return 0;
            else return k + 1; // иначе k == текущая позиция подстроки needle в строке haystack 
           // k показывает смещение в haystack, предполагая, что строка начинается с 1 
    }
    else return 0;  
}
*/
 
#endif
 
_____________________________________________________________________________________________________
 
#include <iostream>
#include "csub.h"
#include <fstream>
#include <istream>
#include <cstring>
#include <cstdio>
#include <string>
#include <vector>
 
using namespace std;
 
void fun(string &text, string &form, int size_s, int &count)
{        
    int entered2 = BoyerMooreHorspool2(text, form);
    if (entered2 == 0) return;
    else
    {
        count++;
        text.erase(0,  entered2 + size_s );
        fun(text, form, size_s, count);             
    }
}
            
int main()
{
     std::locale::global(std::locale("")); 
 
    /*
    string s1 = "abDcDABcd";
    string s2 = "A";
 
    cout << "haystack: "<< s1 << endl;
    cout << "needle: "<< s2 << endl; 
    cout << "result: "<< BoyerMooreHorspool2(s1,s2) ;//<< " " << comp << endl;
   */
    
    //double comp  = 0;
    //double sum_comp = 0;
 
    vector<string> text; //Массив строк (кол-во строк заранее неизвестно)
    string strTmp;
 
    ifstream in("к.txt");
    while(getline(in, strTmp))
        text.push_back(strTmp);
 
    string s = "the";
    int size_s = s.size();
    
    int res_count = 0;
    int count = 0;
    
    for (int i = 0; i < text.size() ; i++)
    {
        string str = text[i];
        int entered = BoyerMooreHorspool2(str, s);
        if (entered != 0)
        {
            res_count += 1;
            str.erase(0, entered + size_s);
            fun(str, s, size_s, count);
        }
    }
 
    cout << "Число повторений " << s << " в тексте: " << res_count + count << endl;
    
    /*
    for (int i = 0; i < text.size() ; i++)
    {
        cout << text[i] << endl;
        cout << endl;
    }
    
    string str2 = "bolted toward the back of the room, barely escaping a shower of glass. Kriss grabbed my";
    string s = "the";
    int count = 0;
    int entered = BoyerMooreHorspool2(str2, s);
    if (entered != 0)
    {
        count++;
        str2.erase(0, entered + s.size() - 1);
        cout << str2 << endl;
        fun(str2, s, s.size(),count); 
    }
    */
}
Добавлено через 19 минут
Прошу прощения, не алгоритм Краскала, а алгоритм Бойера-Мура-Хорспула
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
24.06.2014, 00:09
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Помогите доделать алгоритм Бойера-Мура-Хорспула (C++):

Ошибка в функции поиска подстроки в строке. Алгоритм Бойера-Мура-Хорспула. - C++
Функция получает ссылки на две переменные: haystack и needle строкового типа. В haystack должна содержаться строка, в которой будет...

Алгоритм Бойера и Мура - C++
Добрый день! Помогите пожалуйста написать на С++ алгоритм Бойера и Мура Добавлено через 7 часов 41 минуту Пожалуйста помогите

Алгоритм Бойера — Мура - C++
Доброго времени суток, нет ли у кого-нибудь примера реализации алгоритма Бойера — Мура. Искал в интернете, но там в основном теория,...

Алгоритм Бойера-Мура - C++
Скиньте пожалуйста алгоритм Бойера-Мура

Алгоритм Бойера-Мура поиска подстроки в строке (Js -> C++) - C++
Помогите реализовать алгоритм для с ++ &lt;html&gt; &lt;head&gt; &lt;meta charset=&quot;utf-8&quot; /&gt; &lt;title&gt;Практическое использование курсовой...

Поиск подстроки в строке(алгоритм Бойера-Мура) - C++
Программа находит шаблоны в строке алгоритмом Бойера-Мура и находить должна в строке которая находится в файле. Сам код работает и находит...

0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
24.06.2014, 00:09
Привет! Вот еще темы с ответами:

Очень прошу разъяснить код алгоритма Бойера-Мура - C++
#include &lt;cstdlib&gt; #include &lt;iostream&gt; #include &lt;string&gt; #define ALPHABET_LEN 255 #define NOT_FOUND patlen #define max(a, b)...

Алгоритм Бойлера-Мура - C++
Мой алгоритм Бойлера-Мура находит позицию первого вхождения подстроки в строке, но мне нужны все вхождения. Помогите исправить! #include...

Помогите доделать PacMan! - C++
В универе задали сделать Пакмена. С одной темы на этом форуме взял код и переписал на свой лад #include &quot;col.h&quot; ...

Помогите доделать прогу телефонного справочника - C++
Вот написал с трудом прогу телефонного справочника. Но там нет редактирования записей и поиска по базе. Подскажите пожалуйста как лучше...


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

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

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