重念一次早該補起來的「資料結構與演算法」。這篇筆記下 LCS 最長共同子序列。
課程相關資訊
[連結]：https://hiskio.com/courses/572/lectures/29910
本篇範圍：Chapter 10
請注意：本系列文章為個人對應課程的消化吸收後，所整理出來的內容。換言之，並不一定會包含全部的課程內容，也有可能會添加其他資源來說明。
內容
1. common substring 可以在兩個字串中，找到共同連續的字串
2. common subsequence 是指在兩個字串中，出現的順序一樣，但不需要連續。這可用於兩個字串的相似程度有多高
解法：可以使用遞迴的方式
A. 從兩個字串的最後一位開始執行，如果相同的話，那就將其抽離，並加入到結果的字串中
B. 若不同的話，那就會分別執行兩者，兩者取其大的值。
C. 終止條件是 LCS(“”, “”), LCS(“”, “A”), LCS(“A”, “”) 這三類，當有出現 Empty String 時。
