TWISTED Самая длинная общая подпоследовательность

Меня интересовал особый случай проблемы самой длинной общей подпоследовательности http://en.wikipedia.org/wiki/Longest_common_subsequence_problem Что, если у нас есть две строки из n символов, и гарантируется, что обе они содержат ровно 1 символ и каждый символ из первых n символов алфавита. Как можно улучшить нормальный алгоритм?


string recursion algorithm dynamic-programming induction
person user103260    schedule 20.11.2013    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Вы запрашиваете самую длинную общую подпоследовательность между перестановками. Существует улучшение по сравнению с динамическим программированием, которое вы связали, называемое алгоритмом Робинсона-Шенстеда-Кнута, и оно выполняется за время O (n lg n). Достаточно простой пример того, как это работает в лекциях 7 и 8 этого курса , и гораздо более полное, но сложное объяснение здесь.

person Andy Jones    schedule 29.11.2013