作者sa072686 (小紅)
看板b97902HW
標題[計程] 鋼彈的LCS
時間Wed Oct 29 22:43:06 2008
即題目中提及的 Longest Common Subsequence。
也就是說，找到最長的 Sequence 使其為 s1 與 s2 的 Subsequence。
防一下雷…
故知此 Sequence 必為 s1 之 Subsequence，因此可窮舉 s1 之所有 Subsequence
來檢驗是否為 s2 之 Subsequence，記錄長度最長為何即可。
至於窮舉方式，反正 Subsequence 就是每個字選擇取與不取，因此共 2^n 種。
用遞迴去窮舉即可。
另外一個方法是使用動態規劃的方法。
考慮兩個序列 a, b 長度分別為 n, m，若兩者尾巴一樣，即 a[n] == b[m]，
可知此二序列之 LCS 必為 a, b 去尾後之 LCS 長度 +1。
若以 f(i, j) 代表 a 前 i 個字元及 b 前 i 個字元之 LCS，
則上述即為 f(n, m) = f(n-1, m-1) if a[n] == b[m]
若不相同呢？可知其 LCS 為拿掉 a[n] 或拿掉 b[m] 其中最大者，
因為其實這些情形加上 a[n] 或加上 b[m] 並不會影響 LCS 個數，
擇優錄取即可。故此情形即為：
f(n, m) = max(f(n-1, m), f(n, m-1)) otherwise
可知邊界條件，若其中之一長度為 0，則 LCS 必為 0。
故得：
f(n, m) = 0 if n == 0 || m == 0
至於實作方式有二，一為用兩層迴圈去跑 i, j，
順序無所謂，只要能確保跑到 i, j 時已跑過 (i-1, j), (i-1, j-1), (i, j-1)
即可。
另一為使用遞迴，但由於重覆運算量極大，如 (i, j) 可能被 (i+1, j), (i, j+1)
甚至 (i+1, j+1) 呼叫，可能會算很多次，那麼在它底下的就會被算更多次。
如果每一層都多算一兩次，那麼整體下來就很可怕了…
因此，必須記住哪些是計算過的；就不再計算。
可知 (i, j) 解答是固定的，不因其它外在條件而改變，
因此若是首次遇見，則遞迴求解之，並記錄此問題已被解開、以及答案為何；
下次再遇見，則直接告知答案即可，無須再算。
另有一方法是使用 Longest (Strictly) Increasing Subsequence (LIS)
來對 LCS 做極限優化，不過應該沒必要這樣，要講也更難講…
如果有興趣再私下問我好了。
貼心文末防雷。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.240.202
推 ming1053:你真的講了啊XD 10/29 22:51
推 purplebleed:此法只應天上有,凡人乖乖用迴圈...我是凡人..所以用 10/29 23:01
→ purplebleed:迴圈 = =.....不過有了這一篇也許我也能飛上天~~ 10/29 23:03
推 hrs113355:我是用遞迴去列舉的 跟SA說的第一個方法一樣 10/29 23:05
推 anfranion:真強者出招了XD 10/29 23:06
推 ckclark:樓上很像張爸推文 10/29 23:12
推 matt7983:(天阿~~台大XDDD) 10/29 23:16
推 godgunman:其實那真的是張爸文(!!) 10/29 23:17
推 martinku:好文!看了之後就AC了! 10/30 00:16