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
| #include <iostream>
#include <vector>
#include <locale.h>
int LINE(char*, char*, int, int);
int BM(char*, char*, int, int);
int KMP(char*, char*, int, int);
int main()
{
setlocale(LC_CTYPE, "rus");
char string[] = "паша закрыл всю сессию. паша это не маша.";
char substring[] = "паша";
int k_LINE, k_BM, k_KMP;
int s_size = strlen(string);
int ss_size = strlen(substring);
std::cout << "Строка: " << string << std::endl;
std::cout << "Подстрока: " << substring << std::endl;
k_LINE = LINE(&string[0], &substring[0], s_size, ss_size);
k_BM = BM(&string[0], &substring[0], s_size, ss_size);
k_KMP = KMP(&string[0], &substring[0], s_size, ss_size);
std::cout << "Количество совпадений линейным алгоритмом: " << k_LINE
<< "\nКоличество совпадений алгоритмом Боера-Мура: " << k_BM
<< "\nКоличество совпадений алгоритмом Кнута-Морриса-Пррата: " << k_KMP << "\n";
return 0;
}
int LINE(char *string, char *substring, int s_size, int ss_size) //Линейный поиск
{
int count = 0; //Количество вхождений
int i = 0;
while ((s_size - i) >= ss_size) //Пока возможно вхождение
{
if (string[i] == *substring) //Одинаковый символ
{
bool p = true;
for (int j = 0; j < ss_size; j++) //Цыкл сравнения
{
if (string[i + j] != substring[j])
{
p = false;
break;
}
}
if (p) count++; //Удачная операция
i++;
}
else
i++;
}
return count; //Возврат количества найденых значений
}
//end_symb - позиция конца суффикса
//sufix_size - размер массива суфиксов
int sufix_search(char *substring, int ss_size, int end_symb, int sufix_size) //Заполнение таблицы суфиксов
{
if (end_symb > sufix_size)
return substring[end_symb - sufix_size - 1] != substring[ss_size - sufix_size - 1] &&
memcmp(substring + ss_size - sufix_size, substring + end_symb - sufix_size, sufix_size) == 0; //Если длина суфикса не больше длины строки
else
return memcmp(substring + ss_size - end_symb, substring, end_symb) == 0; //Если больше
}
int max(int a, int b) //Функция возврата максимального
{
if (a > b)
{
return a;
}
else
return b;
}
int BM(char *string, char *substring, int s_size, int ss_size) //Алгоритм Бойера-Мура основная функция
{
int count = 0;
int *arr_sufix = new int[ss_size];
int *arr_stop = new int[34];
for (int i = 0; i < 34; i++) //таблицу стоп-символов заполняем -1
arr_stop[i] = -1;
for (int i = 0; i < ss_size - 1; i++) // В таблицу стоп-символов записывается последнее вхождение в substring
arr_stop[substring[i]] = i;
for (int i = 0; i < ss_size; i++) //Строим таблицу суфиксов
{
int dss_size = ss_size; //Дублируем размер подстроки
while (dss_size && !sufix_search(substring, ss_size, dss_size, i))
dss_size--;
arr_sufix[ss_size - i - 1] = ss_size - dss_size;
}
for (int i = 0; i <= s_size - ss_size; )
{
int position = ss_size - 1;
while (substring[position] == string[i + position])
{
if (position == 0) //Все символы совпали
{
count++;
break;
}
--position;
}
i += max(arr_sufix[position], position - arr_stop[string[position + i]]); //Если нет совпадений переходим к следующему сравнению
}
if (count == 0) //если вхождений нет возвращаем -1
{
return -1;
}
else
return count;
}
std::vector<int> prefix_function(char substring[]) //Префикс функция
{
int ss_size = strlen(substring);
std::vector<int> pi(ss_size);
for (int i = 1; i<ss_size; ++i)
{
int j = pi[i - 1];
while (j > 0 && substring[i] != substring[j])
j = pi[j - 1];
if (substring[i] == substring[j])
++j;
pi[i] = j;
}
return pi;
}
int KMP(char *string, char *substring, int s_size, int ss_size) //Алгоритм Кнута-Морисса-Пратта
{
int kol_sov = 0; //Число вхождений
substring[ss_size] = '&'; //разделитель строки и подстроки
for (int i = 0; i < s_size; i++) //Создаем строку из подстроки и строки
{
substring[ss_size + 1 + i] = string[i];
}
substring[ss_size + s_size + 1] = '\0';
std::vector<int> prefix = prefix_function(substring);
for (int i = 0; i < prefix.size(); i++)
{
if (prefix[i] == ss_size)
kol_sov++;
}
return kol_sov;
} |
(
Сообщение от Fixer_84
