Изменить код алгоритма поиска подстроки в строке

@Nik- · Регистрация: 12.07.2015

Студворк — интернет-сервис помощи студентам

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

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
#include "stdafx.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_string_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() {
    bohr_ini();
    add_string_to_bohr("baabc");
    add_string_to_bohr("ababc");
    find_all_pos("abbxcavb");
    system("PAUSE");
    return 0;
}

@Mesteriis · 22.10.2015, 21:04

Nik-, Чуть мозг не порвал, ей богу дурацкий код, еще раз что хотите изменить?????

@Nik- · 23.10.2015, 17:57 **[ТС]**

С хабрахабра взят. Поменять со string в char, в строке add_string_to_bohr. Работать буду с сигнатурами файлов,поэтому нужно,чтобы и цифры могли присутсвовать в добавлении в бор.

Добавлено через 20 часов 37 минут
Изменил все там, где хотел, но после компиляции программа экстренно завершается и показывает на 82 строчку,ошибка - выход за пределы вектора, как исправить это ?

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
#include "stdafx.h"
#include <iostream>
#include <cstring>
#include <vector>
#include <string>
using namespace std;
const int k = 26, NMAX = 10000;
const int N = 256;
 
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_string_to_bohr(const char* s) {
    int num = 0;
    for (int i = 0; i<N; 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 char* s) {
    int num = 0;
    for (int i = 0; i<N; 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() {
    bohr_ini();
    add_string_to_bohr("ba2abc");
    add_string_to_bohr("ababc");
    find_all_pos("abbxcavba2");
    system("PAUSE");
    return 0;
}

@Dimension · 23.10.2015, 18:03

Сообщение от Nik-

как исправить это ?

написать свой код с самого начала и перестать использовать чужие коды без понимая их работы

@Nik- · 23.10.2015, 18:14 **[ТС]**

Я просил помочь, а не критиковать что-то. И уж поверьте, я тоже не сижу, а занимаюсь решением этой проблемы.

@Dimension · 23.10.2015, 18:27

вам нужно решение через бор?может простенькая префикс функция подойдет?

@Nik- · 23.10.2015, 18:31 **[ТС]**

Через бор не обязательно. Главное, чтобы алгоритм мог относительно быстро искать подстроки в строке, а они будут большие и с цифрами.

@Dimension · 23.10.2015, 18:37

выводит все индексы начиная с которых строка b входит в строку a,работает за линию

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
#include <bits/stdc++.h>
using namespace std;
int main(){
    string s;
    string a, b;
    cin >> a >> b;
    s = b + "$" + a;
    vector<int> v(s.size(), 0);
    for (int i = 1;i < s.size();i++) {
        int t = v[i - 1];
        while (t > 0 && s[t] != s[i])
            t = v[t - 1];
        if (s[i] == s[t])
            t++;
        v[i] = t;
    }
    for (int i = 0;i < s.size();i++) {
        if (v[i] == b.size()) {
            cout << i - 2 * b.size() << " ";
        }
    }
    cin.get(), cin.get();
    return 0;
}

@Nik- · 23.10.2015, 18:44 **[ТС]**

Компилятор ругается на заголовочный файл. Убрал заголовочный файл, ввел 2 строки и консоль просто закрылась.

@Dimension · 23.10.2015, 18:47

добавьте вместо него

C++
1
2
3
#include <vector>
#include <string>
#include <iostream>

@Nik- · 23.10.2015, 18:49 **[ТС]**

Так и сделал. После добавления этих заг. файлов программа заработала, но , как уже и сказал, завершается сразу, после добавления второй строки.

@Dimension · 23.10.2015, 18:51

добавьте system("PAUSE"); с #include <windows.h> либо _getch(); с #include <conio.h>

@Nik- · 23.10.2015, 18:55 **[ТС]**

system("PAUSE") есть.

@Dimension · 23.10.2015, 19:04

ничего не выводит потому что второй строки нет в первой

@Nik- · 23.10.2015, 19:08 **[ТС]**

да, все получилось, спасибо. А что за цифры выводит после того, как нашел строку?

@Dimension · 23.10.2015, 19:12

индексы начала вхождения ,то есть начиная с какого элемента вторая строка встречается в первой ,нумерация с нуля

@Nik- · 23.10.2015, 19:57 **[ТС]**

А что надо сделать, чтобы поддерживались и цифры? Остановился на 13 строке. Компилятор указывает на $ и пишет, что выражение должно относится к целочисленному типу или типу без области видимости.

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
#include <iostream>
#include <string>
#include<vector>
#include<windows.h>
using namespace std;
int main() {
    char* s;
    char* a;
    char* b;
    const int N = 255;
    for (int i = 0; i < N; i++)
        cin >> a[i] >> b[i];
 
    s = b + "$" + a;
    vector<int> v(s.size(), 0);
    for (int i = 1; i < s.size(); i++) {
        int t = v[i - 1];
        while (t > 0 && s[t] != s[i])
            t = v[t - 1];
        if (s[i] == s[t])
            t++;
        v[i] = t;
    }
    for (int i = 0; i < s.size(); i++) {
        if (v[i] == b.size()) {
            cout <<i - 2 * b.size() << " ";
        }
    }
    system("PAUSE");
    return 0;
}

@Dimension · 23.10.2015, 20:04

используйте string вместо char , так же вводите как и раньше

@Nik- · 23.10.2015, 20:19 **[ТС]**

Мне кажется, что в любом случае придется изменять из string в char, т.к. я буду работать с файловым вводом и выводом.

@Dimension · 23.10.2015, 20:26

файловый ввод вывод насколько я знаю и со string работает ,в любом случае можно по символу считывать из файла в char и прибавлять в string

Новые блоги и статьи Все статьи Все блоги /
Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .	Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .	Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .
Мысли в слух kumehtar 18.11.2025 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .	Создание Single Page Application на фреймах krapotkin 16.11.2025 Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .	Фото: Daniel Greenwood kumehtar 13.11.2025	Расскажи мне о Мире, бродяга kumehtar 12.11.2025 — Расскажи мне о Мире, бродяга, Ты же видел моря и метели. Как сменялись короны и стяги, Как эпохи стрелою летели. - Этот мир — это крылья и горы, Снег и пламя, любовь и тревоги, И бескрайние. . .	PowerShell Snippets iNNOKENTIY21 11.11.2025 Модуль PowerShell 5. 1+ : Snippets. psm1 У меня модуль расположен в пользовательской папке модулей, по умолчанию: \Documents\WindowsPowerShell\Modules\Snippets\ А в самом низу файла-профиля. . .

@Mesteriis 599 / 237 / 69 Регистрация: 08.08.2015 Сообщений: 1,637
	22.10.2015, 21:04
	Nik-, Чуть мозг не порвал, ей богу дурацкий код, еще раз что хотите изменить????? 0

@Nik- 20 / 20 / 11 Регистрация: 12.07.2015 Сообщений: 350
	23.10.2015, 18:14 [ТС]
	Я просил помочь, а не критиковать что-то. И уж поверьте, я тоже не сижу, а занимаюсь решением этой проблемы. 0

@Dimension Dimension 595 / 463 / 223 Регистрация: 08.04.2014 Сообщений: 1,710
	23.10.2015, 18:27
	вам нужно решение через бор?может простенькая префикс функция подойдет? 0

@Nik- 20 / 20 / 11 Регистрация: 12.07.2015 Сообщений: 350
	23.10.2015, 18:31 [ТС]
	Через бор не обязательно. Главное, чтобы алгоритм мог относительно быстро искать подстроки в строке, а они будут большие и с цифрами. 0

@Nik- 20 / 20 / 11 Регистрация: 12.07.2015 Сообщений: 350
	23.10.2015, 18:44 [ТС]
	Компилятор ругается на заголовочный файл. Убрал заголовочный файл, ввел 2 строки и консоль просто закрылась. 0

@Nik- 20 / 20 / 11 Регистрация: 12.07.2015 Сообщений: 350
	23.10.2015, 18:49 [ТС]
	Так и сделал. После добавления этих заг. файлов программа заработала, но , как уже и сказал, завершается сразу, после добавления второй строки. 0

@Dimension Dimension 595 / 463 / 223 Регистрация: 08.04.2014 Сообщений: 1,710
	23.10.2015, 18:51
	добавьте system("PAUSE"); с #include <windows.h> либо _getch(); с #include <conio.h> 0

@Nik- 20 / 20 / 11 Регистрация: 12.07.2015 Сообщений: 350
	23.10.2015, 18:55 [ТС]
	system("PAUSE") есть. Миниатюры 0

@Dimension Dimension 595 / 463 / 223 Регистрация: 08.04.2014 Сообщений: 1,710
	23.10.2015, 19:04
	Сообщение было отмечено Nik- как решение Решение ничего не выводит потому что второй строки нет в первой 1

@Nik- 20 / 20 / 11 Регистрация: 12.07.2015 Сообщений: 350
	23.10.2015, 19:08 [ТС]
	да, все получилось, спасибо. А что за цифры выводит после того, как нашел строку? 0

@Dimension Dimension 595 / 463 / 223 Регистрация: 08.04.2014 Сообщений: 1,710
	23.10.2015, 19:12
	индексы начала вхождения ,то есть начиная с какого элемента вторая строка встречается в первой ,нумерация с нуля 1

@Dimension Dimension 595 / 463 / 223 Регистрация: 08.04.2014 Сообщений: 1,710
	23.10.2015, 20:04
	используйте string вместо char , так же вводите как и раньше 1

@Nik- 20 / 20 / 11 Регистрация: 12.07.2015 Сообщений: 350
	23.10.2015, 20:19 [ТС]
	Мне кажется, что в любом случае придется изменять из string в char, т.к. я буду работать с файловым вводом и выводом. 0

@Dimension Dimension 595 / 463 / 223 Регистрация: 08.04.2014 Сообщений: 1,710
	23.10.2015, 20:26
	файловый ввод вывод насколько я знаю и со string работает ,в любом случае можно по символу считывать из файла в char и прибавлять в string 0

Изменить код алгоритма поиска подстроки в строке

Решение