4446
правок
Сравнение с шаблоном для сжатого текста: различия между версиями
Материал из WEGA
Сравнение с шаблоном для сжатого текста (посмотреть исходный код)
Версия от 21:30, 5 ноября 2021
, 5 ноября 2021→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 90: | Строка 90: | ||
'''Теорема 8 (Карккайнен и др. [8]). При использовании модели расстояния Левенштейна задача ACPM может быть решена за время <math>O(k \cdot |P| \cdot |\mathbf{c}(T)| + occ)</math> для LZ78/LZW и за время <math>O(|P| \cdot (k^2 \cdot |\mathcal{D}| + k \cdot |\mathcal{S}|) + occ)</math> для | '''Теорема 8 (Карккайнен и др. [8]). При использовании модели расстояния Левенштейна задача ACPM может быть решена за время <math>O(k \cdot |P| \cdot |\mathbf{c}(T)| + occ)</math> для LZ78/LZW и за время <math>O(|P| \cdot (k^2 \cdot |\mathcal{D}| + k \cdot |\mathcal{S}|) + occ)</math> для регулярных систем коллажей, где k – заданный порог ошибки.''' | ||
| Строка 99: | Строка 99: | ||
'''Теорема 10 (Наварро [14]). Задача RCPM решается за время <math>O(2^{|P|} + |P| \cdot |\mathbf{c}(T)| + occ \cdot |P| \cdot log |P|)</math>, где occ – количество вхождений P в T.''' | '''Теорема 10 (Наварро [14]). Задача RCPM решается за время <math>O(2^{|P|} + |P| \cdot |\mathbf{c}(T)| + occ \cdot |P| \cdot log |P|)</math>, где <math>occ</math> – количество вхождений P в T.''' | ||
== Применение == | == Применение == | ||
