Хотелось бы обсудить алгоритмы, без кода.
Задача: Пусть S и T две последовательности элементов. Найдите общие подпоследовательности между ними, где порядок элементов сохраняется .
Он должен иметь время выполнения O (n + m), где n - это длина S, а m - это длина T. Я также хотел бы сделать предположение, что по большей части две последовательности будут одинаковыми.
Оптимальное решение?: После некоторых исследований, одно из решений, которое представляется оптимальным, - это сначала построить обобщенное суффиксное дерево для двух последовательностей. Затем найдите самую длинную общую подстроку и рассмотрите эту подпоследовательность как часть решения. Затем либо удалите эту подпоследовательность из дерева, либо создайте новое дерево суффиксов с этой подпоследовательностью, удаленной из двух исходных последовательностей, чтобы сформировать S 'и T'. Затем найдите самую длинную общую подстроку между S 'и T' и так далее.
Чтобы проанализировать время выполнения, построение дерева занимает O (n), и вы можете найти длины и начальные позиции самых длинных общих подстрок S и T в O (n + m).
Существуют ли другие (более) практические решения, о которых кто-то знает или может ссылаться на них? Любые опубликованные статьи, в которых рассматривается та же или связанная с этим проблема, о которой вы все знаете? Ввод и конструктивная критика по поводу вышеуказанного решения? Спасибо за ваше время!