Я реализовал решение mlcs с использованием динамического программирования c, и результаты были удовлетворительными. Моя проблема в том, что когда количество последовательностей n увеличивается и эти последовательности довольно длинные, результирующая таблица lcs слишком велика и не может быть сохранена в памяти, и, таким образом, все вылетает.
У меня есть Здесь мы видим решения в переполнении стека, где только предыдущие строки хранятся в памяти, и хотя это работает для построения таблиц, я не могу выполнить возврат и получить общую подпоследовательность, которая является моей конечной целью. Я исследовал и увидел, что для этого доступно несколько оптимизаций, в частности, оптимизация Ханта-Шимански, а также решения, основанные на направленных графах ацикли c, DAG.
Теперь я спрашиваю, есть ли у кого-нибудь ссылка на код, псевдокод, который реализует эти оптимизированные решения (или другие!), так как в настоящее время мне не хватает времени и знаний, чтобы сделать это, и я уверен, что другие люди уже решили это. Буду благодарен за любую идею, обсуждение или источник!