Алгоритм агрегации похожих последовательностей

Question

Допустим, у вас есть список похожих последовательностей, например

a a a a
a b a a a
x a a a a y
...

Вы хотите обнаружить общую совокупность всех этих последовательностей, например

x? a b? a a a y?

где оператор ? указывает, что элемент является необязательным.

Какой алгоритм вы бы использовали?

Answer 1

Посмотрите на алгоритмы выравнивания последовательностей , используемые в биоинформатике.

Более конкретно, поскольку у вас есть список, выравнивание нескольких последовательностей . алгоритм Витерби должен делать.

Answer 2

Возможно, вы захотите проверить алгоритм Смита-Уотермана, который используется для выполнения выравнивания последовательностей.

Answer 3

Я думаю, что если вы преобразуете свой список в суффиксное дерево, это будет очень простое рекурсивное решение, но я не уверен насчет асимптотической сложности