Сравнение с шаблоном для сжатого текста: различия между версиями

Теорема 5 (Кида и др. [9]). Задача CPM для систем коллажей может быть решена за время 0((\T>\ + \S\)- height (T))+\P\2+occ) с использованием O(jDj + jPj2) памяти, где occ – количество вхождений шаблона. Для систем коллажей без усечений коэффициент height(D) опускается.

Алгоритм [ ] состоит из двух этапов. На первом этапе производится предварительная обработка D и P, а на втором – обработка переменных S. На втором этапе имитируется перемещение автомата KMP, работающего на несжатом тексте, с помощью двух функций Jump и Output. Обе эти функции принимают на вход состояние q и переменную X. Первая используется для замены только одного перехода состояния на последовательные переходы состояния автомата KMP для строки X для каждой переменной X из S; вторая – для сообщения обо всех вхождениях шаблона, найденных во время переходов состояния. Пусть S – функция перехода состояний KMP-автомата. Тогда Jump(q;X) = 8{q,X), а Output(q,X) – множество длин jwj непустых префиксов w из X, таких, что S(q, w) является конечным состоянием. Наивная реализация этих двух функций в виде двумерного массива требует памяти J2(|D| - |P|). Структуры данных из [ ] используют только O(jDj + jPj2) памяти, строятся за время O(\T)\ ■ height(D) + jPj2) и позволяют вычислить Jump(q,X) за O(1) времени и перенумеровать множество Output(q, X) за время O(height(D) + I), где I = jOutput(q; X)j. Для систем коллажей без усечений коэффициент height(D) опускается.