Нижние оценки временной и объёмной сложности задачи поиска подслова

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