4446
правок
Сравнение с шаблоном для сжатого текста: различия между версиями
Материал из WEGA
Сравнение с шаблоном для сжатого текста (посмотреть исходный код)
Версия от 21:27, 5 ноября 2021
, 5 ноября 2021→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 73: | Строка 73: | ||
Другой критерий алгоритмов CPM основывается на объеме дополнительной памяти [4]. Алгоритм CPM является | Другой критерий алгоритмов CPM основывается на объеме дополнительной памяти [4]. Алгоритм CPM является [https://en.wikipedia.org/wiki/In-place_algorithm алгоритмом типа inplace (англ.)], если объем дополнительной памяти пропорционален размеру входных данных P. | ||
| Строка 79: | Строка 79: | ||
Существует множество вариантов задачи CPM. Далее некоторые из них будут вкратце рассмотрены. ''Алгоритм сравнения с шаблоном для полностью сжатого текста'' (Fully-compressed pattern matching, FCPM) – это сложный вариант, | Существует множество вариантов задачи CPM. Далее некоторые из них будут вкратце рассмотрены. | ||
''Алгоритм сравнения с шаблоном для полностью сжатого текста'' (Fully-compressed pattern matching, FCPM) – это сложный вариант, в котором и T, и P даны в сжатом формате. Прямолинейная программа представляет собой регулярную систему коллажей с <math>|\mathcal{S}| = 1</math>. | |||
