Задача о наибольшем общем подслове

Пусть даны $m$ слов суммарной длины $n$ и число $d$. Задача о наибольшем общем подслове состоит в нахождении максимального по длине слова, входящего в по крайней мере $d$ из заданных слов.
Известно, что задача может быть решена с использованием линейных по $n$ памяти и времени: в 1973 году Питер Винер предложил решение для частного случая $m = d = 2$, а позже, в 1992 году, Лукас Чи Квонг Хьюи предложил решение и для общего случая.
В докладе будет рассмотрен следующий естественный вопрос: можно ли решить задачу о наибольшем общем подслове, если использовать меньше памяти, но, быть может, чуть больше времени? В качестве частичного ответа на указанный вопрос будет предложена серия алгоритмов, использующих $S = C(S) \cdot s$ памяти и $T = C(T) \cdot n^2 / s$ времени, где $C(S)$, $C(T)$ – константы, а $1 \leq s \leq n$ – параметр алгоритма. Также будет дана нижняя оценка на время работы $T$ алгоритма, использующего $S$ памяти.