\( \newcommand{\ord}[1]{\mathcal{O}\left(#1\right)} \newcommand{\abs}[1]{\lvert #1 \rvert} \newcommand{\floor}[1]{\lfloor #1 \rfloor} \newcommand{\ceil}[1]{\lceil #1 \rceil} \newcommand{\opord}{\operatorname{\mathcal{O}}} \newcommand{\argmax}{\operatorname{arg\,max}} \newcommand{\str}[1]{\texttt{"#1"}} \)

2018年12月31日 星期一

[ Cyclic Longest Common Subsequence ] 環狀最長共同子序列

相信會看我發的文的人應該多少都知道LCS(最長共同子序列)是什麼吧?對於這樣的問題很早以前就有人提出$\ord{nm}$的方法了。
現在如果將問題中的字串改成頭尾相接環狀的字串,我們稱其最長共同子序列為CLCS,例如:
設A,B為頭尾相接環狀字串
A = "aabaa" , B = "aaabb"
CLCS(A,B) = "aaab"
像這樣的問題要怎麼解呢?剛好codeforces上面就有一題:http://codeforces.com/gym/100203/problem/B
為了解決這一題,查閱了不少奇怪的文章,最後給我找到了這篇論文:Solving Cyclic Longest Common Subsequence in Quadratic Time
對於CLCS提出了$\ord{nm}$的演算法,在這裡附上該演算法的實作:

作法大致上是將b字串變成原來的兩倍,然後做一般的LCS,但在過程中要注意更新答案的順序。接著修改DP來源表格,每次將來源表格的第一個row刪掉(reRoot函數),然後計算當前的答案。

當我AC這一題後,我看到了一個非常驚人的作法,也是用DP複雜度是$\ord{nm}$,但是我目前還無法完全理解為何這樣是可行的,而且這樣的做法我也不知道如何回溯找出一組解,只能知道CLCS的長度,希望路過的大大們能提供想法:

沒有留言:

張貼留言