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

Помогите решить алгоритм Боуера-Мура - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Перенос проекта с delphi на Visual C++ http://www.cyberforum.ru/cpp-beginners/thread405299.html
Видели наверное темы мои про конференции. Так вот лауреата взял, теперь к следующей готовлюсь,в Новосиб. И хочу перенести.
C++ Вычисление сумм диагональных элементов матриц Даны в файле 2 матрицы 2 матрицы в файле 3х3 (разделены пробелом) 1 2 3 4 5 6 7 8 9 9 8 7 6 5 4 3 2 1 http://www.cyberforum.ru/cpp-beginners/thread405290.html
Битовые операции C++
Доброго времени суток! Есть задача: Даны два целых без знаковых числа. Остатки от деления их на 16 заносятся соответственно в 4 младших и 4 старших разряда одного байта. Далее нужно вывести результат содержимого полученного байта. Можете помочь, а то я как-то...?
C++ 2-3 дерево
есть у кого пример 2-3 дерева? желательно с выводом и поиском min max спасибо
C++ в чем ошибка? http://www.cyberforum.ru/cpp-beginners/thread405262.html
Даны действительное число а, натуральное число n. Вычислить: 1/a + 1/(a^2) + 1/(a^4) + ... + 1/a^(2^n) #include <stdio.h> #include <stdlib.h> #include <iostream.h> #include <math.h> int main(int argc, char *argv) { int a, n, x, i; cout<<"vvedite a=";
C++ heapsort and pointers очень прошу завтра защита, я физически неуспеваю искать материал и делать слаиды, помогите если у кого есть презентации на темы heapsort and pointers отправьте мне. и еще одно тут нужно написать через Pointers, Arrays of chars, Function,Header File. вот эти функции size clear empty at подробнее

Показать сообщение отдельно
cooller51190555
0 / 0 / 0
Регистрация: 06.05.2011
Сообщений: 34

Помогите решить алгоритм Боуера-Мура - C++

12.12.2011, 15:49. Просмотров 588. Ответов 0
Метки (Все метки)

Задача Последовательность целых чисел в диапазоне от 0 до 100 задана в виде линейного списка. С кла-виатуры вводится другая последовательность. Необходимо, используя алгоритм Боуера-Мура, определить, входит ли вторая последовательность в состав исходной.
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
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
#include <string.h>
#include <limits.h>
#include <stdio.h>
#include <conio.h>
#include <iostream>
 using namespace std; 
 class List
{
public:
        List(List& list);
        List(int num);
        ~List();
        void out_list();
        void add_list(List& list);
        void insert(int elem);
private:
        struct node 
        {
                int info;
                struct node *next;
        };
private:
        node* m_head;
        int count;
};
 
List::List(int num)
{
        m_head=NULL;
        for(int i=0;i<num;i++)
        {
                this->insert(rand()%100);
        }
}
 
List::List(List& list)
{
        m_head=NULL;
        node* p1=list.m_head;
        while(p1)
        {
                this->insert(p1->info); 
                p1=p1->next;
        }       
}
 
void List::insert(int elem)
{
        node* p = m_head;
        node* el = new node;
        el->info = elem;
        el->next = NULL;
        if(!m_head)
        {
                m_head = el;
        }else if(m_head->info>el->info)
        {
                el->next = m_head;
                m_head = el;
        }else
        {
                while(p->next)
                {
                        if(p->info<=el->info && p->next->info>=el->info)
                        {
                                el->next = p->next;
                                p->next = el;
                                break;
                        }
                        p=p->next;
                }
                if(!p->next)
                {
                        p->next = el;
                }
        }
}
List::~List()
{
        node* p =m_head;
        while(p)
        {
                node* temp = p;
                p=p->next;
                delete temp;
        }
}
void List::out_list()
{
        node* p = m_head;
        if(p)
        {
                while(p)
                {
                        cout<<p->info<<' ';
                        p=p->next;
                        
                };
        }else
        {
                cout<<"empty list"<<endl;
        }
        cout<<endl;
}
 
void List::add_list(List& list)
{
        node* p1=list.m_head;
        while(p1)
        {
                this->insert(p1->info); 
                p1=p1->next;
        }       
}
/* Вход: needle+nlen - что искать
 *   offset - позиция конца суффикса; suffixlen - его длина
 * Выход: 1, если есть совпадение суффикса (и нет совпадения более длинного суффикса)
 */
static int suffix_match(const  char *needle, size_t nlen, size_t offset, size_t suffixlen)
{
    if (offset > suffixlen)
        return needle[offset - suffixlen - 1] != needle[nlen - suffixlen - 1] &&
            memcmp(needle + nlen - suffixlen, needle + offset - suffixlen, suffixlen) == 0;
    else
        return memcmp(needle + nlen - offset, needle, offset) == 0;
}
 
static size_t max(size_t a, size_t b)
{
    return a > b ? a : b; 
}
 
/* Вход: haystack - где искать, needle - что искать.
 *   hlen - длина haystack, nlen - длина needle
 * Выход: указатель на первое вхождение needle в haystack, либо NULL
 */
 const char* memmem_boyermoore
    (const  char* haystack, const size_t hlen,
     const  char* needle,  const size_t nlen)
{ 
    size_t *skip = new size_t[nlen];          /* Таблица суффиксов */
    size_t occ[UCHAR_MAX + 1]; /* Таблица стоп-символов */
 
    if(nlen > hlen || nlen <= 0 || !haystack || !needle) 
        return NULL;
 
    /* ПОСТРОЕНИЕ ТАБЛИЦЫ СТОП-СИМВОЛОВ */
 
    /* Заполняем -1 (в Си нумерация символов с 0!!) */
    for(size_t a=0; a<UCHAR_MAX+1; ++a)
        occ[a] = 0;
 
    /* В таблицу occ записывается последнее вхождение в needle  */
    /* (исключая последний символ) */
    for(size_t a = 0; a < nlen - 1; ++a) 
        occ[needle[a]] = a;
 
    /* ПОСТРОЕНИЕ ТАБЛИЦЫ СУФФИКСОВ */  
    /* Упрощённый вариант. Можно реализовать быстрее. */
    for(size_t a = 0; a < nlen; ++a)
    {
        size_t offs = nlen;
        while(offs && !suffix_match(needle, nlen, offs, a))
            --offs;
        skip[nlen - a - 1] = nlen - offs;
    }
 
    /* ПОИСК */
    for(size_t hpos = 0; hpos <= hlen - nlen; )
    {
        size_t npos = nlen - 1;
        /* Сверка needle и haystack с конца */
        while(needle[npos] == haystack[npos + hpos])
        {
            if(npos == 0) 
                return haystack + hpos;
 
            --npos;
        }
        /* Не совпало! */
        hpos += max(skip[npos], npos - occ[haystack[npos + hpos]]);
        /*          ^^^         ^^^^                               */
        /*        суффикс     стоп-символ                          */
    }
    return NULL;
}
 
int main()
{  srand((unsigned)time(NULL));
   List list1(20);
   cout<<"Spisok1"<<endl;
   list1.out_list();
    
    char br[31]; // объявление символьного массива
    char *str1="1234567";
 
    cout<<"Vvedi posledovatelnost 2"<<endl;
    cin>>br;
    const  char *str2 =br;
    const char *str3;
    
 
    str3 = memmem_boyermoore(str1,strlen(str1),str2,strlen(str2));
        
 
    cout<<"Rezultat"<<endl;
    printf(str3);
        _getch();
}
Подскажите как сделать ток чтоб он сравнивал не с последовательностью str1 а со списком который выводит list1.out_list();....
Никак не могу понять....
Всё остальное сделал, а как это сделать не знаю...

Добавлено через 5 минут
C++
1
2
char *str1;
    str1=list1;
Думал сделать просто так но выдаёт естественно ошибку... а как правильно сделать чего-то нигде не найду
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
 
Текущее время: 10:41. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru