Longest Common Subsequence，最长相同子序列（LCS）

-- TOC --

问题分析

Subsequence is not substring.

问题分析

子序列，subsequence，是元素按照原序列内的顺序出现但不一定连续的序列。

sequence:    ABCDEFG
subsequence: ACD, BEFG, ABCDE

LCS问题，就是寻找两个sequence的最长的common subsequence。

S1 =  ACCGGTCGAGTGCGCGGAAGCCGGCCGAA
S2 =  GTCGTTCGGAATGCCGTTGCTCTGTAAA
LCS = GTCGTCGGAAGCCGGCCGAA

本文链接：https://cs.pynote.net/ag/dp/202403147/

-- EOF --

-- MORE --