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

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

Восстановить пароль Регистрация
 
cooller51190555
0 / 0 / 0
Регистрация: 06.05.2011
Сообщений: 34
12.12.2011, 15:49     Помогите решить алгоритм Боуера-Мура #1
Задача Последовательность целых чисел в диапазоне от 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;
Думал сделать просто так но выдаёт естественно ошибку... а как правильно сделать чего-то нигде не найду
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
12.12.2011, 15:49     Помогите решить алгоритм Боуера-Мура
Посмотрите здесь:

Помогите решить алгоритм C++
C++ Алгоритм Бойера-Мура
C++ Ошибка в функции поиска подстроки в строке. Алгоритм Бойера-Мура-Хорспула.
C++ Поиск подстроки в строке(алгоритм Бойера-Мура)
Алгоритм Бойлера-Мура C++
Алгоритм Бойера и Мура C++
C++ Алгоритм Бойера-Мура поиска подстроки в строке (Js -> C++)

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

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