Какова сложность (Big O Notation) операции grep текстового файла, если мы проверяем строку по частичному совпадению?

Рейтинг: 0Ответов: 1Опубликовано: 01.03.2023

Если я правильно понимаю, то сложность операции команды grep с текстовым файлом будет O(n), если мы ищем строку по полному совпадению.

Если мы грепаем файл по частичному совпадению строк, сложность операции увеличится до следующего уровня?

list grep итераторы
Источник: Stack Overflow на русском

Ответы

▲ 1Принят

GNU Grep

The grep command operates partly via a set of automata that are designed for efficiency, and partly via a slower matcher that takes over when the fast matchers run into unusual features like back-references. When feasible, the Boyer–Moore fast string searching algorithm is used to match a single fixed pattern, and the Aho–Corasick algorithm is used to match multiple fixed patterns.

таблицу сравнение алгоритмов поиска подстроки в строке, в том числе и вышеупомянутых можно посмотреть в этой статье - Поиск подстроки в строке