Какова сложность (Big O Notation) операции grep текстового файла, если мы проверяем строку по частичному совпадению?
Если я правильно понимаю, то сложность операции команды grep с текстовым файлом будет O(n), если мы ищем строку по полному совпадению.
Если мы грепаем файл по частичному совпадению строк, сложность операции увеличится до следующего уровня?
Ответы (1 шт):
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.
таблицу сравнение алгоритмов поиска подстроки в строке, в том числе и вышеупомянутых можно посмотреть в этой статье - Поиск подстроки в строке