臺灣博碩士論文加值系統

在本論文中，我們首先定義了兩種基於融合最長共同子序列(MLCS)的變形問題，分別是融合最長共同子序列且子字串長度為t (MLCSt)問題和融合最長共同子序列且子字串長度大於等於t (MLCSt+)問題。這兩個問題討論了MLCS問題分別延伸至LCS問題且子字串長度為t (LCSt)和子字串長度大於等於t (LCSt+)。在本論文中，我們提出了動態規劃(DP)演算法來解決這兩種問題，時間複雜度為O(mnr)，其中m、n和r 分別為A、B和目標序列P的長度。在用於MLCSt+的DP演算法中，我們應用了Ueki等人的技術來降低時間複雜度。另外，我們將對角線概念應用於解決這兩種問題。基於對角線概念的MLCSt演算法的時間複雜度為O(R+(r-L+1)Lm)，MLCSt+演算法的時間複雜度為O(R+(r-L+1)(Lm+R))，其中R為A和P之間以及B和P之間的總配對數量，L是答案的長度。最後我們提出了一些實驗結果來說明我們算法的效率。

In this thesis, we first defi ne two new variants of the merged longest common
subsequence (MLCS) problem. They are the MLCS problem with t-length substrings
(MLCSt) and the MLCS problem with at least t-length substrings (MLCSt+). The
MLCSt and MLCSt+ problems discuss the merged LCS (MLCS) extended from the
LCS problems with t-length substrings (LCSt) and with at least t-length substrings
(LCSt+), respectively. In this thesis, we propose the dynamic programming (DP)
algorithms for solving these two problems in O(mnr) time, where m, n and r are the
lengths of the two main sequences A and B and the target sequence P, respectively.
In the DP algorithm for MLCSt+, we apply the technique of Ueki et al. to reduce the
time complexity. In addition, we apply the diagonal concept to the solving of these
two problem. The time complexity of the diagonal algorithms for solving the MLCSt
problem is O(R + (r -L + 1)Lm) and for MLCSt+ is O(R + (r -L + 1)(Lm + R)),
where R is the number of total match pairs between A and P, and between B and
P, L is the length of the answer. We also present some experimental results to
illustrate the e fficiency of our algorithms.

THESIS VERIFICATION FORM . . . . . . . . . . . . . . . . . . . . . . i
THESIS AUTHORIZATION FORM . . . . . . . . . . . . . . . . . . . . iii
ACKNOWLEDGEMENT . . . . . . . . . . . . . . . . . . . . . . . . . . . iii
CHINESE ABSTRACT . . . . . . . . . . . . . . . . . . . . . . . . . . . . iv
ABSTRACT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . v
LIST OF TABLES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viii
LIST OF SYMBOLS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xi
Chapter 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
Chapter 2. Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.1 The Merged Longest Common Subsequence Problem . . . . . . . . . 5
2.2 The Diagonal Algorithm for Solving the MLCS Problem by Tseng et al. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.3 The Longest Common Subsequence Problem with t-length Substrings (LCSt) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.4 The Longest Common Subsequence Problem with at Least t-length Substrings (LCSt+) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.5 The De nitions of the MLCSt and MLCSt+ Problems . . . . . . . . . 12
Chapter 3. The Algorithms for the MLCSt and MLCSt+ Problems . 15
3.1 The Dynamic Programming Algorithms for MCSt and MLCSt+ . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
3.2 The Diagonal Algorithm for MLCSt . . . . . . . . . . . . . . . . . . . 26
3.3 The Diagonal Algorithm for MLCSt+ . . . . . . . . . . . . . . . . . . 32
Chapter 4. Experimental Results . . . . . . . . . . . . . . . . . . . . . . 42
4.1 The Merged Longest Common Subsequence Problem with t-Length Substrings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
4.2 The Merged Longest Common Subsequence Problem with at least t-Length Substrings . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
4.3 Brief Summary for the Experimental Results . . . . . . . . . . . . . . 52
Chapter 5. Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
BIBLIOGRAPHY . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
Appendixes
A. The Additional Experimental Results of MLCSt . . . . . . . . . . . 57
B. The Additional Experimental Results of MLCSt+ . . . . . . . . . . 70

[1] H. Y. Ann, C. B. Yang, C. T. Tseng, and C. Y. Hor, "Fast algorithms for
computing the constrained LCS of run-length encoded strings," Theoretical
Computer Science, Vol. 432, pp. 1-9, 2012.
[2] A. N. Arslan and o. E gecio glu, "Algorithms for the constrained longest common
subsequence problems," International Journal of Foundations of Computer
Science, Vol. 16, pp. 1099-1109, 2005.
[3] G. Benson, A. Levy, S. Maimoni, D. Noifeld, and B. R. Shalom, "LCSk: A
re ned similarity measure," Theoretical Computer Science, Vol. 638, pp. 11-26, 2016.
[4] G. Benson, A. Levy, and B. R. Shalom, "Longest common subsequence in k
length substrings," Proceedings of the 6th International Conference on Similar-
ity Search and Applications, Vol. 8199, pp. 257-265, 2013.
[5] Y. C. Chen and K. M. Chao, "On the generalized constrained longest common
subsequence problems," Journal of Combinatorial Optimization, Vol. 21, pp. 283-392, 2011.
[6] F. Y. L. Chin, A. D. Santis, A. L. Ferrara, N. L. Ho, and S. K. Kim, "A simple
algorithm for the constrained sequence problems," Information Processing Letters, Vol. 90, pp. 175-179, 2004.
[7] S. Deorowicz, "Bit-parallel algorithm for the constrained longest common subsequence
problem," Fundamenta Informaticae, Vol. 99, pp. 409-433, 2010.
[8] S. Deorowicz and A. Danek, "Bit-parallel algorithms for the merged longest
common subsequence problem," International Journal of Foundations of Computer Science, Vol. 24, pp. 1281-1298, 2013.
[9] S. Deorowicz and S. Grabowski, "E cient algorithms for the longest common
subsequence in k-length substrings," Information Processing Letters, Vol. 114, pp. 634-638, 2014.
[10] Z. Gotthilf, D. Hermelin, and M. Lewenstein, "Constrained LCS: Hardness and
approximation," Proceedings of the 19th Annual Symposium on Combinatorial
Pattern Matching (CPM), Vol. 5029, Pisa, Italy, pp. 255-262, 2008.
[11] S. Grabowski, "New tabulation and sparse dynamic programming based
techniques for sequence similarity problems," Discrete Applied Mathematics, Vol. 201, pp. 96-103, 2016.
[12] G. F. Huang, C. B. Yang, K. T. Tseng, and K. S. Huang, "Diagonal algorithms
for the longest common subsequence problems with t-length and at
least t-length substrings," Proceedings of the 37th Workshop on Combinatorial
Mathematics and Computation Theory, Kaohsiung, Taiwan, pp. 119-127, 2020.
[13] K. S. Huang, C. B. Yang, K. T. Tseng, H. Y. Ann, and Y. H. Peng, "E cient algorithms
for nding interleaving relationship between sequences," Information
Processing Letters, Vol. 105, pp. 188-193, 2008.
[14] S. H. Hung, C. B. Yang, and K. S. Huang, "A diagonal-based algorithm for the
constrained longest common subsequence problem," Proceedings of the 23rd In-
ternational Computer Symposium 2018 (ICS 2018), Vol. 1013, Yunlin, Taiwan, pp. 425-432, 2018.
[15] N. Nakatsu, Y. Kambayashi, and S. Yajima, "A longest common subsequence
algorithm suitable for similar text strings," Acta Informatica, Vol. 18, pp. 171-179, 1982.
[16] F. Paveti c, I. Katani c, G. Matula, G. Zu zi c, and M. Siki c, "Fast and simple
algorithms for computing both LCSk and LCSk+," CoRR, abs/1705.07279, 2018.
[17] F. Paveti c, G. Zu zi c, and M. Siki c, "LCSk++: Practical similarity metric for
long strings," CoRR, abs/1407.2407, 2014.
[18] Y. H. Peng, C. B. Yang, C. T. Tseng, and K. S. Huang, "An algorithm and
applications to sequence alignment with weighted constraint," International
Journal of Foundations of Computer Science, Vol. 21, pp. 51-59, 2010.
[19] Y. H. Peng, C. B. Yang, K. S. Huang, C. T. Tseng, and C. Y. Hor, "E -
cient sparse dynamic programming for the merged LCS problem with block
constraints," International Journal of Innovative Computing, Information and
Control, Vol. 6, pp. 1935-1947, 2010.
[20] A. M. Rahman and M. S. Rahman, "E ective sparse dynamic programming
algorithms for merged and block merged LCS problems," Journal of Computers, Vol. 9(8), pp. 1743-1754, 2014.
[21] Y. T. Tsai, "The constrained longest common subsequence problem," Information Processing Letters, Vol. 88, pp. 173-176, 2003.
[22] C. T. Tseng, C. B. Yang, and H. Y. Ann, "E cient algorithms for the longest
common subsequence problem with sequential substring constraints," Journal
of Complexity, Vol. 29(1), pp. 44-52, 2013.
[23] K. T. Tseng, D. S. Chan, C. B. Yang, and S. F. Lo, "E cient merged longest
common subsequence algorithms for similar sequences," Theoretical Computer Science, Vol. 708, pp. 75-90, 2018.
[24] Y. Ueki, Diptarama, M. Kurihara, Y. Matsuoka, K. Narisawa, R. Yoshinaka,
H. Bannai, S. Inenaga, and A. Shinohara, "Longest common subsequence in
at least k length order-isomorphic substrings," Proceedings of the 43rd Inter-
national Conference on Current Trends in Theory and Practice of Computer
Science, Vol. 10139, Limerick, Ireland, pp. 364-374, 2017.
[25] R. A. Wagner and M. J. Fischer, "The string-to-string correction problem,"
Journal of the ACM, Vol. 21(1), pp. 168-173, 1974.
[26] D. Zhu, L. Wang, T. Wang, , and X. Wang, "A space e cient algorithm for
the longest common subsequence in k-length substrings," Theoretical Computer
Science, Vol. 687, pp. 79-92, 2017.
[27] D. Zhu, L. Wang, T. Wang, and X. Wang, "A simple linear space algorithm for
computing a longest common increasing subsequence," IAENG International
Journal of Computer Science, Vol. 45(3), pp. 472-477, 2018.