Доброго времени суток, читатели, зрители моего канала programmer's notes. Не забывайте подписываться и писать свои комментарии к моим статьям и видео.
Поиск подстроки в строке, явные алгоритмы
Продолжим цикл статей по поиску подстроки в строке. В прошлой статье мы рассматривали использование методов find() и index(). Сегодня рассмотрим явные алгоритмы.
Сегодня рассмотрим два простых, или я бы сказал явных, алгоритмов поиска подстроки в строке. Программа ниже осуществляет поиск подстроки в строке, которые заданы непосредственно в тексте программы. Общий принцип: по-символьное сравнение.
Идея алгоритма в следующем. Идёт по-символьное сравнение символов строки и первого символа подстроки. Если совпадение обнаружено, далее начинается по-символьное сравнение знаков подстроки и знаков строки. Если все символы совпали, то мы нашли совпадение.
Следующая программа совсем проста. Идея её заключается в использовании слайсов (срезов). Происходит сравнение подстроки и соответствующего среза строки. Понятно, что по-символьное сравнение здесь завуалировано - отдано библиотеке Python.
Сегодня всё. Замечу только, что мы не рассматривали вопрос, который обсуждался в прошлой статье. Это откуда начинать поиск следующей подстроки, если поиск увенчался успехом: со следующего символа или с символа, за найденным отрезком. Это, уже, я думаю, тривиально и не стоит обсуждать этот вопрос.
В заключении приведу ещё один простой способ поиска с использованием метода startswith() строки. Метода возвращает True, если строка начинается с данного префикса. Всё очень просто и элегантно
#!/usr/bin/python3
s = 'qwertyqwertyerwtywertyywertrrwerty'
sb = 'werty'
res = [i for i in range(len(s)) if s.startswith(sb, i)]
print(*res, sep='\n')
Ну, пока всё!
Пишите свои предложения и замечания, и занимайтесь программированием, а также проектированием баз данных, хотя бы для поддержания уровня интеллекта.