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

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

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Реализовать функцию, меняющую местами первый столбец матрицы с последним http://www.cyberforum.ru/cpp-beginners/thread1215508.html
Помогите, пожалуйста,написать эту программу_( Из файла file1.txt считывается двумерная вещественная матрица А, из файла file2.txt матрица В(Размеры задаются в файлах).Естественно предварительно создаем file1.txt и file2.txt. Вот сами задания: 1)Реализовать ф-ю,вычисляющую выражение А*В. 2)Реализ-ть ф-ю, меняющую местами первый столбец с последним.
C++ Шифрование текста при помощи таблицы. Прокомментируйте код можете ли вы написать алгоритм этой программы и описать каждое действие, если не сложно, пожалуйста программа: Зашифровывает текст следующим образом: записывает его в матрицу по строкам, а затем переписывает по спирали от центра. Символы "_" нужны чтобы до заполнить матрицу в том случае когда во введенной строке не хватает символов для полного заполнения квадратной матрицы сама программа... http://www.cyberforum.ru/cpp-beginners/thread1215501.html
C++ Вывести на экран, четное или нечетное число
что бы выводило чотное оно или нет
Перевод градусов в радианы C++
задание выглядит вот так :Объект: угол (градусы, минуты, секунды). Реализовать базовые операции над углами и дополнительно: преобразовать в радианы и из радианов, преобразовать в грады и из градов, получить дополнительный угол. Операции должны производиться с учётом целых оборотов, т.е. результат всегда от 0 до 360. проблема с последним пунктом , теоретически понимаю что секунды и минуты < 60,...
C++ Найти минимальный по значению элемент и записать его на начало массива, высвободив для него место путем смещ http://www.cyberforum.ru/cpp-beginners/thread1215449.html
Генерировать значения элементов одномерного массива с помощью генератора псевдослучайных чисел, введя количество элементов массива с клавиатуры. найти минимальный по значению элемент и записать его на начало массива, высвободив для него место путем смещения элементов массива вправо.
C++ Определить количество различных цифр, содержащихся в десятичной записи каждого элемента массива натуральных ч Определить количество различных цифр, содержащихся в десятичной записи каждого элемента массива натуральных чисел. Использовать структуру для хранения цифрового символа из массива чисел и количества различных цифр в его записи. подробнее

Показать сообщение отдельно
Krooxe
Сообщений: n/a

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

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