Бойер-Мур. Поиск подстроки в строке

22.04.2015, 19:52. Показов 805. Ответов 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
int BMSearch(char *string, char *substring)
{
int sl, ssl;
int res = -1;
sl = strlen(string);            
ssl = strlen(substring);        
if (sl == 0)                    
cout << "Неверно задана строка\n";
else if (ssl == 0)              
cout << "Неверно задана подстрока\n";
else {
int i, Pos;                                         
int BMT[256];                               
for (i = 0; i < 256; i++)
BMT[i] = ssl;
for (i = ssl - 1; i >= 0; i--)              
if (BMT[(short)(substring[i])] == ssl)      
BMT[(short)(substring[i])] = ssl - i - 1;
Pos = ssl - 1;
while (Pos < sl)
if (substring[ssl - 1] != string[Pos])
Pos = Pos + BMT[(short)(string[Pos])];
else
for (i = ssl - 2; i >= 0; i--){
if (substring[i] != string[Pos - ssl + i + 1]) {
Pos += BMT[(short)(string[Pos - ssl + i + 1])] - 1;
break;
}
else
if (i == 0)
return Pos - ssl + 1;
cout<<"\t"<< i << endl;
}
}
 
}

cpp_developer

Эксперт

20123 / 5690 / 1417

Регистрация: 09.04.2010

Сообщений: 22,546

Блог

22.04.2015, 19:52

Ответы с готовыми решениями:

Не получается реализовать поиск подстроки в строке. Бойер-Мур
Нужно чтобы выводило количество совпадений каждым алгоритмом. Получился Боера-Мура считает не всегда правильно. Линейный алгоритм всё...

Боуер Мур. поиск подстроки
Написал код, но он некорректно ищет подстроку. В зависимости где находится искомый элемент в тексте. Может вы найдете ошибку? #include...

Поиск подстроки в строке и вывод подстроки
Удалите пожалуйста, разобрался

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.

raxper

Эксперт

30234 / 6612 / 1498

Регистрация: 28.12.2010

Сообщений: 21,154

Блог

22.04.2015, 19:52

Помогаю со студенческими работами здесь

Ввести с клавиатуры строку. Найти шаблон во введенной строке (поиск подстроки в строке)
Помогите написать программу. Ввести с клавиатуры строку. Ввести с клавиатуры коротенькую строку - шаблон. Найти шаблон во введенной строке....

Поиск подстроки в строке
Здравствуйте, помогите исправить программу. Здесь представлен алгоритм поиска подстроки в строке. У меня считается количество вхождений...

Поиск подстроки в строке
Мне нужно с помощью регулярного выражения выбрать первую подстроку, начинающуюся на символ “b” и заканчивающуюся на символ “e” var...

Поиск подстроки в строке
Задача: найти и вывести количество вхождений строки в подстроку и вывести индексы, начиная с единицы. Все работает правильно, но в подобных...

Поиск подстроки в строке
Доброго всем времени суток!!!Требуется решить следующую задачу. Ввести с клавиатуры две строки. Сравнить их. Если вторая строка...

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

Или воспользуйтесь поиском по форуму:

Новые блоги и статьи Все статьи Все блоги /
Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки Neotwalker 08.03.2026 Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд. Даже если у вас. . .	Модульная разработка через nuget packages DevAlt 07.03.2026 Сложившийся в . Net-среде способ разработки чаще всего предполагает монорепозиторий в котором находятся все исходники. При создании нового решения, мы просто добавляем нужные проекты и имеем. . .	Модульный подход на примере F# DevAlt 06.03.2026 В блоге дяди Боба наткнулся на такое определение: В этой книге («Подход, основанный на вариантах использования») Ивар утверждает, что архитектура программного обеспечения — это структуры,. . .	Управление камерой с помощью скрипта OrbitControls.js на Three.js: Вращение, зум и панорамирование 8Observer8 05.03.2026 Содержание блога Финальная демка в браузере работает на Desktop и мобильных браузерах. Итоговый код: orbit-controls-threejs-js. zip. Сканируйте QR-код на мобильном. Вращайте камеру одним пальцем,. . .
SDL3 для Web (WebAssembly): Синхронизация спрайтов SDL3 и тел Box2D 8Observer8 04.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-sync-physics-sprites-sdl3-c. zip На первой гифке отладочные линии отключены, а на второй включены:. . .	SDL3 для Web (WebAssembly): Идентификация объектов на Box2D v3 - использование userData и событий коллизий 8Observer8 02.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-collision-events-sdl3-c. zip Сканируйте QR-код на мобильном и вы увидите, что появится джойстик для управления главным героем. . . .	Реалии Hrethgir 01.03.2026 Нет, я не закончил до сих пор симулятор. Эта задача сложнее. Не получилось уйти в плавсостав, но оно и к лучшему, возможно. Точнее получалось - но сварщиком в палубную команду, а это значит, в моём. . .	Ритм жизни kumehtar 27.02.2026 Иногда приходится жить в ритме, где дел становится всё больше, а вовлечения в происходящее — всё меньше. Плотный график не даёт вниманию закрепиться ни на одном событии. Утро начинается с быстрых,. . .

Наверх