4551
правка
Сходство между сжатыми строками: различия между версиями
Перейти к навигации
Перейти к поиску
м
Сходство между сжатыми строками (посмотреть исходный код)
Версия от 23:01, 24 апреля 2022
, 24 апреля 2022→Открытые вопросы
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 112: | Строка 112: | ||
== Открытые вопросы == | == Открытые вопросы == | ||
Сложность задачи в наихудшем случае не вполне понятна. Для метрики самой длинной общей подпоследовательности найдены некоторые результаты с временной сложностью выше O( | Сложность задачи в наихудшем случае не вполне понятна. Для метрики самой длинной общей подпоследовательности найдены некоторые результаты с временной сложностью выше O(nm' + n'm) при вычислении сходства двух строк, закодированных при помощи длин серий [1, 11, 12]. Остается открытым вопрос о распространении этих результатов на метрику расстояния Левенштейна, метрику взвешенного расстояния редактирования и метрику аффинного штрафа за гэп. | ||