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

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

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

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

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

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

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

Если тут есть кто на с++ и кому нужен код этого алгоритма, то вот он: ``` 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; } } ```

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

+?

+?

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

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

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

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

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

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

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

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

со 2 раза все очевидно)

почему?

ты что дебил камрад ? забудь вообще про программирование, твое - это дворы подметать, купи себе метелку в Леруа за 50 рублей

@@JonhSliver Болеете? Хотел бы пожелать скорейшего выздоровления, но не рискну ввиду тяжелого состояния пациента.