Когда перечисление завершено, вы можете проследить обратно через массив, чтобы восстановить подпоследовательность из шагов, которые вы сделали. то есть, когда вы перемещаетесь назад от последней записи в массиве, каждый раз, когда вы встречаете совпадение, вы просматриваете его в любой из последовательностей (используя координату из массива) и добавляете его в подпоследовательность.
аюсь найти самую длинную общую последовательность из 3 или более строк. В статье Википедии есть отличное описаниекак это сделать для 2 строк, но я немного не уверен, как расширить это до 3 или более строк.
Существует множество библиотек для поиска LCS из 2 строк, поэтому я хотел бы использовать одну из них, если это возможно. Если у меня есть 3 строки A, B и C, допустимо ли найти LCS для A и B как X, а затем найти LCS для X и C, или это неправильный способ сделать это?
Я реализовал это в Python следующим образом:
import difflib
def lcs(str1, str2):
sm = difflib.SequenceMatcher()
sm.set_seqs(str1, str2)
matching_blocks = [str1[m.a:m.a+m.size] for m in sm.get_matching_blocks()]
return "".join(matching_blocks)
print reduce(lcs, ['abacbdab', 'bdcaba', 'cbacaa'])
Это выводит "ba", однако это должно быть "baa".