УДК 519.712

О сложности поиска вхождений подстроки в множество строк / Е. М. Перпер. // Вестн. Моск. ун-та. Сер. 1, Математика. Механика. 2018. № 3. С. 16-21.

Рассматривается задача поиска вхождений подстроки в множество строк: пусть дано множество строк, требуется для произвольной подстроки найти все ее вхождения в строки из этого множества. Исследуются алгоритмы осуществления такого поиска, приведены нижняя оценка времени работы этих алгоритмов и оценки объема памяти для самых быстрых (по порядку) алгоритмов.

Ключевые слова: подстрока, строка, вхождение, поиск вхождений подстроки, нижняя оценка, верхняя оценка.

Библиогр. 7.