LCS 最長共同子序列(未完待續)

Longest Common Subsequence

• 原來以為這是一個演算法，但它其實是個LCS的問題，目的在找出兩個以上的字串中，最長的共同字串。
• 子字串與子序列的差別：子字串必須是字串中的連結部份，子序列則不是必需。

問題的定義

• 有兩個長度為m的字串S，與長度為n的字串T，我們必須找到S與T中的最長子共同子字串，一般稱之為k共同子字串問題。給定一個字串集合S = {S1, ..., Sk}，其中|Si| = ni且Sigma ni = N。2 ≤ k ≤ K，最長字串最少要有k長度。

解法有兩種，分別為suffix tree與dynamic programming，其中

• suffix tree的量級分析為 O(n + m)
• dynamic programming的量級分析為 O( nm )