LCS (Longest Common Subsequence) 字元串最長公共子串算法

lcs (longest common subsequence) 算法用于找出兩個字元串最長公共子串。

算法原理：

(1) 将兩個字元串分别以行和列組成矩陣。

(2) 計算每個節點行列字元是否相同，如相同則為 1。

(3) 通過找出值為 1 的最長對角線即可得到最長公共子串。

　 人 民 共 和 時 代

中 0, 0, 0, 0, 0, 0

華 0, 0, 0, 0, 0, 0

人 1, 0, 0, 0, 0, 0

民 0, 1, 0, 0, 0, 0

共 0, 0, 1, 0, 0, 0

和 0, 0, 0, 1, 0, 0

國 0, 0, 0, 0, 0, 0

為進一步提升該算法，我們可以将字元相同節點(1)的值加上左上角(d[i-1, j-1])的值，這樣即可獲得最大公用子串的長度。如此一來隻需以行号和最大值為條件即可截取最大子串。

民 0, 2, 0, 0, 0, 0

共 0, 0, 3, 0, 0, 0

和 0, 0, 0, 4, 0, 0

算法實作：

轉自：http://www.rainsts.net/article.asp?id=767