0 / 0 / 0
Регистрация: 03.03.2019
Сообщений: 6
1

Бор. Нужно дописать функцию удаления строки из бора

03.03.2019, 17:04. Показов 1161. Ответов 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
#include "pch.h"
#include <iostream>
#include <cstring>
#include <vector>
#include <string>
using namespace std;
const int k = 26, NMAX = 10000;
struct bohr_vrtx {
    int next_vrtx[k], pat_num, suff_link, auto_move[k], par, suff_flink;
    bool flag;
    char symb;
};
vector<bohr_vrtx> bohr;
vector<string> pattern;
bohr_vrtx make_bohr_vrtx(int p, char c) {
    bohr_vrtx v;
    memset(v.next_vrtx, 255, sizeof(v.next_vrtx));
    memset(v.auto_move, 255, sizeof(v.auto_move));
    v.flag = false;
    v.suff_link = -1;
    v.par = p;
    v.symb = c;
    v.suff_flink = -1;
    return v;
}
void bohr_ini() {
    bohr.push_back(make_bohr_vrtx(0, '$'));
}
void add_str_to_bohr(const string& s) {
    int num = 0;
    for (int i = 0; i < s.length(); i++) {
        char ch = s[i] - 'a';
        if (bohr[num].next_vrtx[ch] == -1) {
            bohr.push_back(make_bohr_vrtx(num, ch));
            bohr[num].next_vrtx[ch] = bohr.size() - 1;
        }
        num = bohr[num].next_vrtx[ch];
    }
    bohr[num].flag = true;
    pattern.push_back(s);
    bohr[num].pat_num = pattern.size() - 1;
}
bool is_string_in_bohr(const string& s) {
    int num = 0;
    for (int i = 0; i < s.length(); i++) {
        char ch = s[i] - 'a';
        if (bohr[num].next_vrtx[ch] == -1) {
            return false;
        }
        num = bohr[num].next_vrtx[ch];
    }
    return true;
}
int get_auto_move(int v, char ch);
int get_suff_link(int v) {
    if (bohr[v].suff_link == -1)
        if (v == 0 || bohr[v].par == 0)
            bohr[v].suff_link = 0;
        else
            bohr[v].suff_link = get_auto_move(get_suff_link(bohr[v].par), bohr[v].symb);
    return bohr[v].suff_link;
}
int get_auto_move(int v, char ch) {
    if (bohr[v].auto_move[ch] == -1)
        if (bohr[v].next_vrtx[ch] != -1)
            bohr[v].auto_move[ch] = bohr[v].next_vrtx[ch];
        else
            if (v == 0)
                bohr[v].auto_move[ch] = 0;
            else
                bohr[v].auto_move[ch] = get_auto_move(get_suff_link(v), ch);
    return bohr[v].auto_move[ch];
}
int get_suff_flink(int v) {
    if (bohr[v].suff_flink == -1) {
        int u = get_suff_link(v);
        if (u == 0)
            bohr[v].suff_flink = 0;
        else
            bohr[v].suff_flink = (bohr[u].flag) ? u : get_suff_flink(u);
    }
    return bohr[v].suff_flink;
}
void check(int v, int i) {
    for (int u = v; u != 0; u = get_suff_flink(u)) {
        if (bohr[u].flag) cout << i - pattern[bohr[u].pat_num].length() + 1 << " " << pattern[bohr[u].pat_num] << endl;
    }
}
void find_all_pos(const string& s) {
    int u = 0;
    for (int i = 0; i < s.length(); i++) {
        u = get_auto_move(u, s[i] - 'a');
        check(u, i + 1);
    }
}
int main()
{
    string y;
    bohr_ini();
    string ll;
    int kod;
    while (true)
    {
 
 
        cout << "1 - add str\n" << "2 - find str\n"<<"0 - exit\n";
        cin >> kod;
        switch (kod) {
        case 1:
            cout << "input str\n";
            cin >> ll;
            add_str_to_bohr(ll);
            break;
        case 2:
            cout << "input str\n";
            cin >> y;
            find_all_pos(y);
            break;
        case 0:
            exit(0);
 
        }
    }
    
}
__________________
Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
03.03.2019, 17:04
Ответы с готовыми решениями:

Дописать функцию удаления
Нужно сделать функцыю удаления, а я незнаю как, помогите... #include &lt;conio.h&gt; #include...

Что такое бор/побитовый бор?
Доброго времени суток! Недавно увидел способы решения задач с помощью &quot;бора&quot;. Можете подсказать...

Нужно исправить ошибки в коде и дописать функцию
В 17-ой строке компилятор выдает ошибку invalid operands of types 'int()' and 'int()' to binary...

Нужно составить программу изображения атома водорода Бора-Резерфорда
Ребята помогите пожалуйста нужно составить такую программу

0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
03.03.2019, 17:04
Помогаю со студенческими работами здесь

К коду нужно дописать функцию (void VidAlphabet - сведения о абонентах в алфавитном порядке)
*Main* #include &quot;Header.h&quot; #include &lt;iostream&gt; using namespace std; void...

Нужно написать функцию compress для удаления повторяющихся букв в слове
Function - Compress(s,t). Purpose - замена в строке s множественных вхождений символа t на одно. ...

Реализовать функцию удаления пробелов из заданной строки
есть программа которая удаляет пробелы, но нужно написать ее так что бы она работала через 2...

Как реализовать функцию удаления строки из файла?
Помогите пожалуйста.Как удалить определенную строку из файла?

Написать функцию для удаления строки из двумерного массива
. Написать функцию для удаления строки из двумерного массива. Оставшиеся строки должны быть...

Пытаюсь создать функцию удаления строки. Не могу понять в чём ошибка
function connect() { $connect = mysql_connect('localhost', 'frank', 'delgado') or...


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2022, CyberForum.ru