Finding Constrained Longest Common Subsequences between Two Run-Length Encoded Strings

[[abstract]]在本文中主要探討利用兩個Run-length encoded的字串來解決限制的最長共同子序列(The constrained longest common subsequence，簡稱為CLCS)問題，CLCS是先給定兩個長度大於零的字串以及一個限制的字串，之後在兩個長度大於零的字串中找出包含限制字串的最長共同子序列。我們會介紹關於最長共同子序列(The longest common subsequence，簡稱為LCS)及限制的最長共同子序列(The constrained longest common subsequence，簡稱為CLCS)的相關論文與研究，也提出一個有效的演算法來解決CLCS的問題，並且會使用許多淺顯易懂的例子與圖表來解釋本篇論文最重要的想法，並且分析探討此演算法的證明與時間複雜度。[[abstract]]In this paper, we shall discuss how to solve the constrained longest common subsequence (CLCS) problem between two Run-length encoded strings. Given two run-length encoded strings X and Y and a constrained sequence P, a sequence Z is a constrained longest common subsequence for X and Y with respect to P if Z is a longest sequence of X and Y such that P is a subsequence of Z. We shall propose an efficient algorithm to solve the CLCS problem. The time complexity of our algorithm is O [ r (mN + Mn – mn) + S ], where string X has M characters and m runs, string Y has N characters and n runs and P has r characters and S are grids without calculating of Xi = Yj = Pk block.[[note]]碩