Faster subsequence recognition in compressed strings

Вычисления, производимые над сжатыми строками, являются одним из ключевых подходов к обработке массивных объемов данных. В статье рассматриваются задачи локального распознавания подпоследовательностей в последовательностях, сжатых при помощи SLP-программ. Сежельски и др. предложили алгоритм для задачи локального распознавания, работающий за время $O(\overline mn^2\log n)$, где $\overline m$ – длина SLP-сжатого текста, а $n$ – длина несжатого образца. В данной статье предлагается алгоритм, работающий за время $O(\overline mn^{1.5})$. Этот алгоритм может быть также использован для вычисления наиболее длинной общей подпоследовательности для сжатого текста и несжатого фрагмента за время $O(\overline mn^{1.5})$. Известно, что для сжатого фрагмента эта проблема является NP-трудной. Библ. – 22 назв.