#2. Алгоритм Бойера-Мура-Хорспула

#2. Алгоритм Бойера-Мура-Хорспула | Алгоритмы на Python

Рет қаралды 30,358

selfedu

Күн бұрын

Пікірлер: 58

@Bah1918 3 жыл бұрын

Вы не перестаёте удивлять . СПАСИБО

@vladimirfolomeev5697 3 жыл бұрын

Спасибо за знания, Ваш канал просто находка для становления специалиста.

@sekastrashes Жыл бұрын

спасибо за видео. Мало таких полезных каналов как ваш

@ЕрвандАгаджанян-в3к 3 жыл бұрын

Урок просто нереальный! Спасибо!

@friend1cat 3 жыл бұрын

Мне это нахрен не нужно, но это меня развивает. Спасибо, Сергей. Продолжайте удивлять!

@АделяМахиянова-е1ч 2 жыл бұрын

спасибо большое, вы спасли меня от ошибок на сессии

@qqgl-x6p 8 ай бұрын

люблю вас, вы растите олимпиадников

@thegreatpresto 3 жыл бұрын

Вас очень приятно слушать

@ЕлизаветаАлферова-э2д Жыл бұрын

Спасибо большое за видео!

@neponiatniichell9508 Жыл бұрын

Если я не ошибаюсь, то это лучший алгоритм поиска нужной строки в тексте

@fghinty7623 3 жыл бұрын

круто!

@СарматПересветов 5 ай бұрын

Большое спасибо)

@TRVQ2 2 жыл бұрын

Можно просто как-то так, к примеру: def find_bmh_my(text, pattern): if (len_pattern := len(pattern)) > (len_text := len(text)): return -1 shifts = {} for i, v in enumerate(pattern): if v not in shifts: shifts[v] = i + 1 shift = (len_pattern_minus_one := len_pattern - 1) while shift < len_text: p, t = len_pattern_minus_one, shift while p >= 0 and text[t] == pattern[p]: p, t = p-1, t-1 if p == -1: return t + 1 shift += shifts.get(text[shift], len_pattern) return -1

@yurik-r5l Жыл бұрын

Спасибо за Ваши уроки! Но, либо я что-то не могу понять, либо здесь неточность. На 6:20 Вы говорите, что при несовпадении не последних символов в образе и строке, смещение выбирается по не совпавшему символу образа. Мне кажется более правильно будет так. В этом случае смещение выбирается по символу СТРОКИ, соответствующему последнему символу образа.

@luckytima2315 3 жыл бұрын

Спасибо большое ))) Только не бросайте Django :(

@sainco3036 3 жыл бұрын

Спасибо.

@ВиталийКенарь 2 жыл бұрын

спасибо)

@АлександрШеремет-я7е Жыл бұрын

Если несовпадающий символ не самый правый/последний в образе то смещение берем по: 1. У вас: по несовпадающему символу образа 2. Вот тут: kzbin.info/www/bejne/gXq4eYqDrMaph8k по последнему символу образа 3. А вот тут kzbin.info/www/bejne/hGeqZ3uMrK9nrbM : по несовпадающему символу СТРОКИ Почему такие разночтения ?

@0ver4ance Жыл бұрын

Потому что автор основную идею алгоритма не объяснил. Суть идеи в том, что у нас есть "стоп-символ". Это тот символ, который стоит в тексте под последним символом шаблона. В этом случае: больше метеоданные данные стоп-символ буква "и". А в этом случае: большие метеданные данные уже буква "о". То есть после каждого смещения шаблона стоп-символ меняется. И основная идея алгоритма в том, чтобы в случае, если у нас происходит несоответствие символов в месте, то нам нужно подогнать под стоп-символ последнее вхождение стоп-символа в шаблоне если он есть в шаблоне, если его нет то просто сместить шаблон на всю его длину. Но может возникнуть тогда проблема, что если у нас стоп-символ есть в шаблоне и он находится именно в последней позиции шаблона в единственном экземпляре, то тогда возникнет вечный цикл. Это соответствует следующей ситуации: больше метеоданные данные В этом случае мы просто двигаем шаблон на всю его длину. Вот и вся идея, которую можно реализовать по-разному, поэтому у авторов, которые рассказывают конкретные реализации, но при этом не рассказывают саму идею алгоритма и возникают такие вопросы

@_SkyDancer 8 ай бұрын

А как искать в обратную сторону с конца строки и до начала этим алгоритмом можно?

@НикитаХлобыстов0 8 ай бұрын

ну можешь переверунть строку и образ сразу после их объявления) а результат (если образ есть в строке) переобъяви >>> результат = длинна строки - 1 - результат

@Dream_on_345 3 жыл бұрын

a = input('Пишите строка: ') b = input('Пишите элемент которые вы хотите найти индекс: ') if len(b) > len(a): print('Такой элемент нет в строке!!!') else: x = [] for i in range(len(a)): if a[i:len(b)+i] == b: x.append(i) if len(x) == 0: print('Такой элемент нет в строке!!!') else: print('В строке есть ', len(x), ' элемент. Индекс: ', x) Я разработал собственный алгоритм может этот алгоритм раньше была. Но я разработал его собственный головой. Этот алгоритм найдёт все элементы которые надо найти в строке. Пожалуйста памагите проверить правильность этого алгоритма

@hamzarahatbekov4536 3 жыл бұрын

@bektursunkabylov1883 3 жыл бұрын

@kan4317 3 жыл бұрын

Str.find() Или element in string - возвращает булево значение

@maksdemkovych8884 3 жыл бұрын

@@hamzarahatbekov4536сложность большая , автор в начале видео говорил об этом

@pilina_ 2 жыл бұрын

спасибо, ваш код мне более понятен!

@Иван-х8ж2ф Жыл бұрын

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

@god_of_cringe Жыл бұрын

Знаю поздно, но отвечу. В программе это учитывается, ведь если мы встретили последний символ в образе мы его добавили,а если мы его добавили, условие не выполнится и мы не будем добавлять этот символ с длинной строки, а оставим как до этого добавили.

@exe88cution 3 жыл бұрын

Я так понимаю, этот алгоритм быстрее и проще предыдущего в этом плейлисте?

@selfedu_rus 3 жыл бұрын

Скорее, он просто другой. Реализуется проще, но по скорости в зависимости от данных.

@exe88cution 3 жыл бұрын

@@selfedu_rus спасибо за ответ)

@artyomspb6820 3 жыл бұрын

Супер, я попробовал по запускать код, но он меня бросает в бесконечный цикл, break не срабатывает не подскажите в чем проблема??

@selfedu_rus 3 жыл бұрын

Обновил программу, возможно это было из-за отсутствия переменной j в области видимости цикла while. Если будут проблемы, укажите строку и образ, для которых запускаете алгоритм.

@rpuropu 3 жыл бұрын

Вы ещё и за патчами питона успеваете следить).. ф-строки увидел) материал старый, а код современный)

@shalnayalala 3 жыл бұрын

Программа выдает неправильный индекс (5), если искать образ "kasha" в строке "dasha dasha kasha" :(

@selfedu_rus 3 жыл бұрын

Да, была ошибочка в программе (если несовпадение для первого символа, то j=0 и делался вывод, что образ найден). Поправил, выложил на github измененный вариант. Скачивайте и наслаждайтесь! )) Спасибо!

@gleck8212 Жыл бұрын

А если в образе будет символ `*` ?) Боюсь, что тогда программа полетит)

@gleck8212 Жыл бұрын

Если тут есть кто на с++ и кому нужен код этого алгоритма, то вот он: ``` namespace Bower_Moore { typedef struct { std::unordered_map table; size_t other_chars; } offset_table; size_t get_size_str(char* str) { size_t size = 0; while (str[size]) { size++; } return size; } bool contains(offset_table* table, char key) { return table->table.find(key) != table->table.end(); } offset_table create_table(char* image) { offset_table table; size_t size_image = get_size_str(image); for (size_t i = size_image - 2, j = 1; (int)i >= 0; i--, j++) { if (!contains(&table, image[i])) { table.table[image[i]] = j; } } if (!contains(&table, image[size_image - 1])) { table.table[image[size_image - 1]] = size_image; } table.other_chars = size_image; return table; } int find(char* str, char* substr) { offset_table templ = create_table(substr); size_t size_str = get_size_str(str); size_t size_substr = templ.other_chars; if (size_str >= size_substr) { size_t i = size_substr - 1; while (i < size_str) { size_t j; size_t k = 0; bool flag = false; for (j = size_substr - 1; (int)j >= 0; j--) { if (str[i - k] != substr[j]) { size_t off; if (j == size_substr - 1) { off = (contains(&templ, str[i])) ? templ.table[str[i]] : templ.other_chars; } else { off = templ.table[substr[j]]; } i += off; flag = true; break; } k++; } if (!flag) { return i - k + 1; } } } return -1; } } ```

@hanmahanma5067 9 ай бұрын

Пхахаха попробовал так и вышло

@tedarcher9120 3 жыл бұрын

Как сделать так, чтобы искал все включения подстроки в строку, у меня находит только первое

@selfedu_rus 3 жыл бұрын

Все верно, здесь только первое. Немного фантазии, поменять код и все у вас получится!

@OneOfWun-n2g 3 жыл бұрын

у тебя получилось? если да, то подскажи пожалуйста

@sDerrnit18 3 жыл бұрын

@@OneOfWun-n2g Если первый индекс вхождения - 5, то ты уже проверил первые 5 элементов на вхождение подстроки. Теперь осталось проверить оставшуюся строку на вхождение. Т.е. строку начиная с индекса 5+1 до n.

@mrmccoy8812 2 жыл бұрын

@@sDerrnit18 если такимспособом попытаться найти 'xxx' в 'xxxx', то такой подход работает неправильно