Спасибо за Ваши уроки! Но, либо я что-то не могу понять, либо здесь неточность. На 6:20 Вы говорите, что при несовпадении не последних символов в образе и строке, смещение выбирается по не совпавшему символу образа. Мне кажется более правильно будет так. В этом случае смещение выбирается по символу СТРОКИ, соответствующему последнему символу образа.
Можно просто как-то так, к примеру: 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
Если несовпадающий символ не самый правый/последний в образе то смещение берем по: 1. У вас: по несовпадающему символу образа 2. Вот тут: ruclips.net/video/KIUHWMwavQg/видео.html по последнему символу образа 3. А вот тут ruclips.net/video/N6G6HVwJ4wQ/видео.html : по несовпадающему символу СТРОКИ Почему такие разночтения ?
Потому что автор основную идею алгоритма не объяснил. Суть идеи в том, что у нас есть "стоп-символ". Это тот символ, который стоит в тексте под последним символом шаблона. В этом случае: больше метеоданные данные стоп-символ буква "и". А в этом случае: большие метеданные данные уже буква "о". То есть после каждого смещения шаблона стоп-символ меняется. И основная идея алгоритма в том, чтобы в случае, если у нас происходит несоответствие символов в месте, то нам нужно подогнать под стоп-символ последнее вхождение стоп-символа в шаблоне если он есть в шаблоне, если его нет то просто сместить шаблон на всю его длину. Но может возникнуть тогда проблема, что если у нас стоп-символ есть в шаблоне и он находится именно в последней позиции шаблона в единственном экземпляре, то тогда возникнет вечный цикл. Это соответствует следующей ситуации: больше метеоданные данные В этом случае мы просто двигаем шаблон на всю его длину. Вот и вся идея, которую можно реализовать по-разному, поэтому у авторов, которые рассказывают конкретные реализации, но при этом не рассказывают саму идею алгоритма и возникают такие вопросы
Здравствуйте. Почему в программе, при формировании таблицы смещений, когда формируем последний символ, не учитывается то, что этот последний символ может совпадать с другим символом из образа? Как в образе "зорро", например.
Знаю поздно, но отвечу. В программе это учитывается, ведь если мы встретили последний символ в образе мы его добавили,а если мы его добавили, условие не выполнится и мы не будем добавлять этот символ с длинной строки, а оставим как до этого добавили.
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) Я разработал собственный алгоритм может этот алгоритм раньше была. Но я разработал его собственный головой. Этот алгоритм найдёт все элементы которые надо найти в строке. Пожалуйста памагите проверить правильность этого алгоритма
ну можешь переверунть строку и образ сразу после их объявления) а результат (если образ есть в строке) переобъяви >>> результат = длинна строки - 1 - результат
Обновил программу, возможно это было из-за отсутствия переменной j в области видимости цикла while. Если будут проблемы, укажите строку и образ, для которых запускаете алгоритм.
Да, была ошибочка в программе (если несовпадение для первого символа, то j=0 и делался вывод, что образ найден). Поправил, выложил на github измененный вариант. Скачивайте и наслаждайтесь! )) Спасибо!
@@OneOfWun-n2g Если первый индекс вхождения - 5, то ты уже проверил первые 5 элементов на вхождение подстроки. Теперь осталось проверить оставшуюся строку на вхождение. Т.е. строку начиная с индекса 5+1 до n.
Вы не перестаёте удивлять . СПАСИБО
Спасибо за знания, Ваш канал просто находка для становления специалиста.
спасибо за видео. Мало таких полезных каналов как ваш
Урок просто нереальный! Спасибо!
люблю вас, вы растите олимпиадников
спасибо большое, вы спасли меня от ошибок на сессии
Вас очень приятно слушать
Мне это нахрен не нужно, но это меня развивает. Спасибо, Сергей. Продолжайте удивлять!
Спасибо большое за видео!
Большое спасибо)
Если я не ошибаюсь, то это лучший алгоритм поиска нужной строки в тексте
Спасибо за Ваши уроки! Но, либо я что-то не могу понять, либо здесь неточность. На 6:20 Вы говорите, что при несовпадении не последних символов в образе и строке, смещение выбирается по не совпавшему символу образа. Мне кажется более правильно будет так. В этом случае смещение выбирается по символу СТРОКИ, соответствующему последнему символу образа.
круто!
Можно просто как-то так, к примеру:
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
Спасибо.
Спасибо большое ))) Только не бросайте Django :(
спасибо)
Если несовпадающий символ не самый правый/последний в образе то смещение берем по:
1. У вас: по несовпадающему символу образа
2. Вот тут: ruclips.net/video/KIUHWMwavQg/видео.html по последнему символу образа
3. А вот тут ruclips.net/video/N6G6HVwJ4wQ/видео.html : по несовпадающему символу СТРОКИ
Почему такие разночтения ?
Потому что автор основную идею алгоритма не объяснил. Суть идеи в том, что у нас есть "стоп-символ". Это тот символ, который стоит в тексте под последним символом шаблона. В этом случае:
больше метеоданные
данные
стоп-символ буква "и".
А в этом случае:
большие метеданные
данные
уже буква "о".
То есть после каждого смещения шаблона стоп-символ меняется.
И основная идея алгоритма в том, чтобы в случае, если у нас происходит несоответствие символов в месте, то нам нужно подогнать под стоп-символ последнее вхождение стоп-символа в шаблоне если он есть в шаблоне, если его нет то просто сместить шаблон на всю его длину. Но может возникнуть тогда проблема, что если у нас стоп-символ есть в шаблоне и он находится именно в последней позиции шаблона в единственном экземпляре, то тогда возникнет вечный цикл. Это соответствует следующей ситуации:
больше метеоданные
данные
В этом случае мы просто двигаем шаблон на всю его длину.
Вот и вся идея, которую можно реализовать по-разному, поэтому у авторов, которые рассказывают конкретные реализации, но при этом не рассказывают саму идею алгоритма и возникают такие вопросы
Здравствуйте.
Почему в программе, при формировании таблицы смещений, когда формируем последний символ, не учитывается то, что этот последний символ может совпадать с другим символом из образа? Как в образе "зорро", например.
Знаю поздно, но отвечу. В программе это учитывается, ведь если мы встретили последний символ в образе мы его добавили,а если мы его добавили, условие не выполнится и мы не будем добавлять этот символ с длинной строки, а оставим как до этого добавили.
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)
Я разработал собственный алгоритм может этот алгоритм раньше была. Но я разработал его собственный головой. Этот алгоритм найдёт все элементы которые надо найти в строке. Пожалуйста памагите проверить правильность этого алгоритма
+?
+?
Str.find()
Или
element in string - возвращает булево значение
@@hamzarahatbekov4536сложность большая , автор в начале видео говорил об этом
спасибо, ваш код мне более понятен!
А как искать в обратную сторону с конца строки и до начала этим алгоритмом можно?
ну можешь переверунть строку и образ сразу после их объявления)
а результат (если образ есть в строке) переобъяви >>> результат = длинна строки - 1 - результат
Я так понимаю, этот алгоритм быстрее и проще предыдущего в этом плейлисте?
Скорее, он просто другой. Реализуется проще, но по скорости в зависимости от данных.
@@selfedu_rus спасибо за ответ)
Супер, я попробовал по запускать код, но он меня бросает в бесконечный цикл, break не срабатывает не подскажите в чем проблема??
Обновил программу, возможно это было из-за отсутствия переменной j в области видимости цикла while. Если будут проблемы, укажите строку и образ, для которых запускаете алгоритм.
Программа выдает неправильный индекс (5), если искать образ "kasha" в строке "dasha dasha kasha" :(
Да, была ошибочка в программе (если несовпадение для первого символа, то j=0 и делался вывод, что образ найден). Поправил, выложил на github измененный вариант. Скачивайте и наслаждайтесь! )) Спасибо!
Вы ещё и за патчами питона успеваете следить).. ф-строки увидел) материал старый, а код современный)
А если в образе будет символ `*` ?) Боюсь, что тогда программа полетит)
Если тут есть кто на с++ и кому нужен код этого алгоритма, то вот он:
```
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;
}
}
```
Пхахаха попробовал так и вышло
Как сделать так, чтобы искал все включения подстроки в строку, у меня находит только первое
Все верно, здесь только первое. Немного фантазии, поменять код и все у вас получится!
у тебя получилось? если да, то подскажи пожалуйста
@@OneOfWun-n2g Если первый индекс вхождения - 5, то ты уже проверил первые 5 элементов на вхождение подстроки. Теперь осталось проверить оставшуюся строку на вхождение. Т.е. строку начиная с индекса 5+1 до n.
@@sDerrnit18 если такимспособом попытаться найти 'xxx' в 'xxxx', то такой подход работает неправильно
а почему в 9 строке не :
for i in range(M[-2], -1, 1):
?? мы же с индексами работаем чи шо я прост новичок )
не такой уж и очевидный, после первой половины пошагового объяснения, я бы не смог собрать это в программу
со 2 раза все очевидно)
когда я увидел код, то глаза закровоточили....
почему?
почему?
@@only_girlz он нулевый еще
К сожалению, похоже на фокус - кролик из рукава. Ни одно утверждение не доказано, как и не доказана и работоспособность алгоритма.
ты что дебил камрад ?
забудь вообще про программирование, твое - это дворы подметать, купи себе метелку в Леруа за 50 рублей
@@JonhSliver Болеете? Хотел бы пожелать скорейшего выздоровления, но не рискну ввиду тяжелого состояния пациента.
Здесь алгоритм должен быть по букве ы потому как она редкая