1. Зарегистрируйтесь на сайте repl.it;
2. Перейдите в раздел my repls;
3. Нажмите кнопку Start coding now! - если вы приступаете впервые, или New Repl - если у вас уже есть работы;
4. В списке языков выберите тот язык, который изучаете;
5. Код пишите в левой части окна - в редакторе кода;
6. Чтобы посмотреть результат выполнения файла, нажмите на кнопку Run. Результат появится в правой части окна;
7. После окончания работы скопируйте ссылку на ваш repl в адресной строке браузера;
8. Скопированную ссылку (ваше решение ДЗ) нужно отправить на проверку. Для этого перейдите в личный кабинет на сайте netology.ru, в поле комментария к домашней работе вставьте скопированную ссылку и отправьте работу на проверку;
Давайте применим упрощённый алгоритм Рабина-Карпа для поиска подстроки в строке, но теперь в шаблоне будет один спец-символ *, который будет означать, что подойдёт любая буква.
Давайте рассмотрим на примере. Строка, в которой будем искать: Alibaba or Alibubab? I do not know!. В качестве шаблона возьмём b*b. Есть три подстроки, который подойдёт под этот шаблон: bab (начинается на позиции 3), bub (начинается на позиции 14) и второй bab (начинается на позиции 16).
Давайте для этого модифицируем алгоритм Рабина-Карпа. Мы всё ещё будем использовать упрощённую версию, где в качестве хеша считаем просто сумму кодов символов. В чём же будет состоять модификация? Вместо того чтобы считать хеш на всём шаблоне и сравнивать его с хешами на всех символов очередного кандидата на найденную подстроку, будем считать хеш на всём шаблоне без учёта символа *, а из хеша кандидата вычитать код символа, который стоит на позиции, соответствующей позиции * в шаблоне. Также при равенстве хешей мы будем проверять на ревенство все символы, пропуская позицию с *, тк в неё подойдёт любой символ текста.
Заметим, что тогда если есть подстрока, подходящая под шаблон, то хеш шаблона и хеш кандидата будут совпадать. Также, ничего нам не мешает всё также динамично поддерживать хеш кандидата, подсчитывая его из хеша предыдущего кандидата за O(1). Итоговая асимптотика будет такая же, как и у обычного Рабина-Карпа.
def search(source, pattern):
if source короче pattern:
return Такой подстроки точно нет!
found = []
pattern_hash = сумма кодов символов в pattern без учёта *
asterik_position = позиция '*' в pattern
for start от 0 до длина(source) - длина(pattern) + 1
if start == 0:
window_hash = сумма кодов первых длина(pattern) символов source
window_hash -= код символа в source на позиции asterik_position
else:
window_hash -= код символа в source на позиции start-1
window_hash += код символа в source на позиции start+длина(pattern) - 1
window_hash += код символа в source на позиции где была '*' у прошлого кандидата
window_hash -= код символа в source на позиции где стоит '*' у текущего кандидата
if window_hash == pattern_hash:
for i от 0 до длина(pattern):
if pattern[i] != '*' И source[start + i] != pattern[i]:
не подходит
если подошёл, то добавим start в found
return found
- Напишите функцию поиска шаблона в строке по схеме, данной выше
- Проверьте её на примере выше, убедитесь что ответы совпали
- Загрузите ваше решение на сайт repl.it, отправьте ссылку на него на проверку.