Доброго времени суток, читатели, зрители моего канала programmer's notes. Не забывайте подписываться и писать свои комментарии к моим статьям и видео.
Еще алгоритм поиска подстроки в строке
Еще один алгоритм поиска подстроки в строке. Он в принципе лежит на поверхности. Если до сих пор поиск осуществлялся последовательным движением по строке и сравнением, то возникает вопрос: а может мы в начале поищем подозрительные точки (индексы): т.е. получим список, где искать, а потом уже проверим, нет ли совпадений.
Можно искать просто по первому символу подстроки. Ниже представлена такая программа. Вхождение символа в строке s помещается в список ls. После этого уже проходим по индексам в ls и проверяем всю строку.
Усовершенствуем программу. Во-первых, искать ведь не обязательно только один символ, можно искать целый срез. Возможно это будет более оптимально, если подобрать его длину. Во-вторых, сравнивать нужно не всю строку, а только оставшийся кусок. Ниже представлен усовершенствованный вариант.
Ну и, наконец, для гурманов перепишем программу из рис. 2 следующим образом.
#!/usr/bin/python3
s = 'qwertyqwertyerwtywertyywertrrwerty'
sb = 'werty'
ll, n, m = len(sb), 0, 3
k = len(s) - ll + 1
print("Всего:", len([print(j) for j in [i for i in range(k) if s[i:i+m] == sb[0:m]] if sb[m:] == s[j+m:j+ll]]))
Красиво, да? Пишите однострочные алгоритмы, очень поднимает настроение.
Лишний раз подчеркну одну важную идею, которая проходит красной нитью в сегодняшней статье. В начале мы отбираем те места в строке, которые потенциально могут содержать искомую подстроку. На этом этапе мы сразу отбрасываем те места, которые заведомо не подходят.
Ну, пока всё!
Пишите свои предложения и замечания, и занимайтесь программированием, а также проектированием баз данных, хотя бы для поддержания уровня интеллекта.
