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

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

Войти
Регистрация
Восстановить пароль
 
cooller51190555
0 / 0 / 0
Регистрация: 06.05.2011
Сообщений: 34
#1

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

12.12.2011, 15:49. Просмотров 597. Ответов 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;
Думал сделать просто так но выдаёт естественно ошибку... а как правильно сделать чего-то нигде не найду
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
12.12.2011, 15:49
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Помогите решить алгоритм Боуера-Мура (C++):

Помогите решить алгоритм - C++
:)

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

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

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

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

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

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
12.12.2011, 15:49
Привет! Вот еще темы с ответами:

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

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

помогите решить - C++
1- составить прогу для решения уравнения см фото. примерное решение ,но тут проблема в уравнении int main() { float a, b,...

Помогите решить - C++
ЭТО ЗАДАНИЕ Position of &quot;-1&quot;. In the given NxM matrix find the LAST position of the minus one(-1). If it will be no &quot;-1&quot; value in...


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

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

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