Люблю, когда кто-то пишет посты вместо меня. Точнее не вместо меня. Просто пишут крутые статьи, а я могу просто их вам показать вместо того, чтобы самому заниматься расписыванием. Вот так правильно.
Поиск подстроки в строке.
Есть такой чувак Андрей Гейн. У него есть канал на youtube и канал в тг: @andgein_notes. В конце декабря он написал про 2 текстовые версии о поиске подстроки в строке, которые он выложил в свой блог.
В первой он рассказывает о поиске конкретного паттерна в тексте:
- наивном подходе
- префикс функции и алгоритме Knuth–Morris–Pratt
- далее про Boyer–Moore алгоритм
- и в конце про Two-Way
Сначала прочитайте это замечательное полотно, а потом давайте посмотрим, как использовать продвинутые сёрчеры строк в C++.
В
<functional> есть 3 сёрчера, которые вы можете использовать для поиска строк. Первый -- std::default_searcher. Этот сёрчер, как и все другие, должен передаваться третьим аргументом в алгоритм std::search. Сам сёрчер принимает себе pattern, который ищется в тексте:
auto it = std::search(text.begin(), text.end(), std::default_searcher(pattern.begin(), pattern.end()));
Такой сёрчер будет использовать стандартный алгоритм поиска подстроки в строке.
Не дефолтными сёрчерами могут быть:
- std::boyer_moor_searcher
- std::boyer_moore_horspool_searcher
Пользуемся ими точно так же, как и стандартным.
Если посмотреть на реализацию, например, boyer_moor_search, то можно увидеть ровно описанные Андреем вещи (например, прекомпьют разных табличек).
Из интересного, в шаблоне так же можно передать хеш функцию, которая используется для описанной bas character эвристики: в общем случае мы работаем не только с
char, а с любым произвольным типом символов, так что нужно уметь складывать их в хеш-таблицу, чтобы понимать, сколько символов мы можем скипнуть при очередном мисматче.Если приглядеться на дефолтный сёрчер, то можно понять, что там много не надо и при желании можно и свой реализовать. Можно писать и общего вида алгоритмы, которые будут пробрасывать сёрчеры в
std::search. И пока и всё. Двигаемся ко второй лекции, где освещены продвинутые способы:
- Ахо-Корасик
- суффиксный бор
- суффиксное дерево
- суффиксный автомат
Читается конечно не за секунду. Информации много. Иногда надо вдумываться. Но зато есть вопросы на подумать с подсказками и ответами. Или вопросы, где можно себя проверить.
Прям качественный обучающий материал. Кайфуйте.