Доброго времени суток, читатели, зрители моего канала programmer's notes. Не забывайте подписываться и писать свои комментарии к моим статьям и видео.
Поиск подстроки в строке. Простые алгоритмы с использованием стандарных инструментов find и index
Начну не большую подборку статей о поиске подстроки в строке. Статей будет несколько. Некоторые, возможно будут удивлены, что имеется несколько алгоритмов поиска подстроки в строке.
Сегодня простейшие алгоритмы с использованием стандартных инструментов. В Python есть средства поиска, которые можно использовать для нахождения всех вхождений одной строки в другую.
У строк в Python есть два метода, с помощью которых можно найти все подстроки в строке. Это метод find() и метод index(). Входные параметры у них одинаковы: первый параметр - подстрока, которую ищем. Два следующих параметра необязательны: откуда начинаем поиск (по умолчанию с первого символа), и как символом (номером) заканчиваем поиск (по умолчанию это конец строки). Собственно это и всё, теперь нужно смотреть сами алгоритмы. В стандартном python нет функции, которая бы искала все вхождения одной строки в другой, что-то типа findAll(), поэтому му будем реализовать подобный алгоритм непосредственно в программе.
Представленные ниже программы все осуществляют поиск подстроки в строке. И строка и подстрока заданы непосредственно в тексте программы. Разница только в деталях алгоритмов, вот этим мы сейчас и займёмся.
Рассмотрим программу на рис. 1. Метод find() возвращает индекс начала найденной подстроки. Если строка не найдена, то функция возвращает -1. Это как раз признак того, что поиск нужно заканчивать. Поиск также заканчиваться, если оставшаяся часть строки короче строки для поиска. Это проверка if b > sz. Есть ещё одна важная деталь. Если строка найдена, то следующий поиск начинается со следующего символа (b=i+1).
Программа на рис. 2 представляет тот же алгоритм, что и на рис. 1, но, как видим более компактна. Просто оба условия перенесены непосредственно в условие while. Кроме этого используется моржовый оператор ':='.
Программа на рис. 3 просто изменённая программа с рис. 1. Смысл изменения в следующем. Если найдена строка, то следующий поиск нужно начинать не со следующего символа, а после найденной подстроки: b=i+l1. Можно привести пример. Если есть строка 'wwww', сколько будет в ней подстрок 'ww' - 3 или 2. Если 2, то это как раз к программе из рис. 3.
Метод index() такой же, как и find(). Но если подстрока не найдена, то в случае с методом index() выбрасывается исключение. Поиск с помощью index() представлен на рис. 4.
Ну и в заключении статьи просто приведу пример, чисто методический. Ну, принято всё-таки алгоритмы в виде функций оформлять. Ну вот даватйе и оформим алгоритм из рисунка 1
Функция search() из рис. 5 возвращает список начальных индексов найденных подстрок. Ничего нового я, конечно, не открыл. Просто поместил алгоритм в функцию.
Ну, пока всё!
Пишите свои предложения и замечания, и занимайтесь программированием, а также проектированием баз данных, хотя бы для поддержания уровня интеллекта.